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);
}
}
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
ReplyDeleteone 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