3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ so root, root->left->right and root->right->left are in the same column? \$\endgroup\$ – hoffmale Jul 11 '18 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.