Binary Tree Traversal

Binary Tree Traversal:

Breadth-First 
    1. Level Order traversal

Depth-First 
    1. Pre-Order. 
2. In-Order. <left> <root> <right>
3. Post-Order. <right> <left> <root>



Pre-Order: node visiting order = <root> <left> <right>
Steps:  
   1. Visit root.
2. Visit Left Sub-Tree.
3. Visit Right Sub-Tree.

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree.


In-Order: (nodes are processed in ascending order)
Node visiting order =  <left> <root> <right>
Steps:  
   1. Visit Left Sub-Tree.
2. Visit root.
3. Visit Right Sub-Tree.

In case of binary search trees (BST), Inorder traversal gives nodes in ascending order. To get nodes of BST in descending order, a variation of Inorder traversal where Inorder itraversal s reversed, can be used.

Post-Order: 
Node visiting order =  <left> <right> <root>
Steps:  
   1. Visit Left Sub-Tree.
2. Visit Right Sub-Tree.
3. Visit root.

Postorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree.

private void PreOrder(Node node){
 if(node == null) return;
 
 System.out.println(""+node.key+", "+node.value);
 PreOrder(node.left);
 PreOrder(node.right);
}

private void inOrder(Node node){
 if(node == null) return;
 
 inOrder(node.left);
 System.out.println(""+node.key+", "+node.value);
 inOrder(node.right);
}

private void postOrder(Node node){
 if(node == null) return;
 
 postOrder(node.left);
 postOrder(node.right);
 System.out.println(""+node.key+", "+node.value);
} 

Level-Order: 

public void leveOrder() {
 Queue<Node> queue = new LinkedList<Node>();
 levelOrder(queue, root);
}

private void levelOrder(Queue<Node> queue, Node node) {
 if (node == null)
  return;

 System.out.println("" + node.key + ", " + node.value);
 if (node.left != null)
  queue.add(node.left);
 if (node.right != null)
  queue.add(node.right);
 levelOrder(queue, queue.poll());
}