Monday, July 20, 2015

Binary Tree traversal - vertically and horizontally

Binary tree traversals are one of my favorite coding problems. They can follow into two categories: travel the tree horizontally level by level; or travel the tree vertically level by level.

For example, we have binary tree below:
     1
 2     3
4 5 6  7

horizontal traversal will output:
1
2 3
4 5 6 7

a variance of above is zig-zag traveral, which generate the below:
1
2 3
7 6 5 4

vertical traversal will output:
4
2
1 5 6
3
7

Here is the code:

/*
     * vertical traversal of binary tree
     */
    public static void verticalTraversal(Node root){
        Map<Integer, List<Node>> store = new HashMap<Integer, List<Node>>();
        verticalTraversalHelper(root, 0, store);
        int min=Integer.MAX_VALUE, max=Integer.MIN_VALUE;
        for(int k : store.keySet()){
            if(min>k)
                min = k;
            if(max<k)
                max = k;
        }
       
        for(int vLevel=min; vLevel<=max; vLevel++){
            for(Node n: store.get(vLevel)){
                System.out.print(n.data+" ");
            }
            System.out.println();
        }
    }
   
    private static void verticalTraversalHelper(Node node, int vLevel, Map<Integer, List<Node>> store){
        if(node==null)
            return;
        if(!store.containsKey(vLevel))
            store.put(vLevel, new ArrayList<Node>());
        store.get(vLevel).add(node);
       
        verticalTraversalHelper(node.left, vLevel--, store);
        verticalTraversalHelper(node.right, vLevel++, store);
       
    }
   
    /*
     * horizontally zig-zag traversal of tree
     * using 2 stacks
     */
    public static void zigZag(Node root){
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(root);
       
        int level = 0;
        while(!s1.isEmpty()){
            while(!s1.isEmpty()){
            Node  cur = s1.pop();
            if(level%2==0){
                if(cur.left!=null)
                    s2.push(cur.left);
                if(cur.right!=null)
                    s2.push(cur.right);
            }else{
                if(cur.right!=null)
                    s2.push(cur.right);
                if(cur.left!=null)
                    s2.push(cur.left);
            }
            }
           
            level++;
            s1 = s2;
            s2 = new Stack<Node>();
        }
    }
   
    /*
     * level traversal of tree using a Queue
     */
    public void levelTraversal(Node root){
        Deque<Node> q = new ArrayDeque<Node>();
        q.add(root);
        while(!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.data);
            if(cur.left!=null)
                q.add(cur.left);
            if(cur.right!=null)
                q.add(cur.right);
        }
    }
  

2 comments:

  1. vertical is interesting. my 2 solutions for vertical print: https://github.com/allenlipeng47/algorithm/blob/master/src/main/java/com/pli/project/algorithm/tree/VerticalPrint.java

    ReplyDelete
    Replies
    1. one thing I should refine the vertical traversal is that i need to sort the nodes on the same vertical level by their horizontal level. this is simply recording their horizontal levels then sort.

      Delete