I am trying to code for both recursive and iterative approach to a problem.
Below is a recursive code to print the nodes of binarytree column wise. Basically I have count of root as 0 and if I move left I decrement count by 1 and if I move right I increment the count by 1:
public void printcolumnOrder_recursive(Tree curr,int count){
if(curr == null) return;
if(hm.get(count)!=null){
List l = hm.get(count);
l.add(curr.data);
hm.put(count, l);
}
else{
List l = new ArrayList<Integer>();
l.add(curr.data);
hm.put(count,l);
}
printcolumnOrder_recursive(curr.left,count-1);
printcolumnOrder_recursive(curr.right,count+1);
}
I converted it to an iterative approach:
Stack<Tree> st = new Stack<Tree>();
Stack<Integer> ct = new Stack<Integer>();
Tree node = curr;
st.push(node);
ct.push(0);
while(!st.isEmpty()){
Tree temp=st.pop();
int count = ct.pop();
if(hm.get(count)!=null){
List l = hm.get(count);
l.add(temp.data);
hm.put(count, l);
}
else{
List l = new ArrayList<Integer>();
l.add(temp.data);
hm.put(count,l);
}
if(temp.right!=null){
st.push(temp.right);
ct.push(count+1);
}
if(temp.left!=null){
st.push(temp.left);
ct.push(count-1);
}
}
for(Integer key: hm.keySet()){
for(Integer i: hm.get(key)){
System.out.print(" " + i);
}
System.out.println("");
}
Both implementations work fine.
I have used 2 stacks in the iterative approach, one for nodes in a tree and the other for count.
Do we need a stack for count? Is there a better way to do it?