Tree Traversal

Here is the tree which we are going to traverse in many ways.  Here is the very broad definition of what tree represents in data structure.
In java it is represented as TreeNode which consists of data (40 for root node) and left and right node.

1:  package com.research.tree;  
2:  public class TreeNode   
3:  {   
4:       int data;   
5:       TreeNode left;   
6:       TreeNode right;   
7:       TreeNode(int data)   
8:       {   
9:            this.data=data;   
10:       }   
11:  }   

There are many traversal techniques to traverse a tree but in most of the interviews these 6 traversals are asked to perform. Here is each one in detail. First three traversals (pre-order, post-order, and in-order) are also called Depth-First search because the search tree is deepened as much as possible on each child before going to the next sibling.

• Pre-Order:
  1. Display the data part of the root (or current node).
  2. Traverse the left subtree by recursively calling the pre-order function.
  3. Traverse the right subtree by recursively calling the pre-order function.
  4. Here is the result of pre-order traversal of above tree

                     40, 20, 10, 84, 30, 60, 50, 70
                5. Pictorial representation:

       6. Program: We are using recursion as described above to programmatically traverse the tree.

1:       public void preOrder(TreeNode node){  
2:            if(node != null){  
3:                 System.out.print(node.data+", ");  
4:                 preOrder(node.left);   
5:                 preOrder(node.right);  
6:            }  
7:       }  

• Post-Order:
  1. Traverse the left subtree by recursively calling the post-order function.
  2. Traverse the right subtree by recursively calling the post-order function.
  3. Display the data part of the root (or current node).
  4. Here is the result of pre-order traversal of above tree

                     84, 10, 30, 20, 50, 70, 60, 40
                5. Pictorial representation:

6. Program: We are using recursion as described above to programmatically traverse the tree.

1:       public void postOrder(TreeNode node){  
2:            if(node != null){  
3:                 postOrder(node.left);  
4:                 postOrder(node.right);  
5:                 System.out.print(node.data+", ");  
6:            }  
7:       }  

• In-Order:
  1. Traverse the left subtree by recursively calling the in-order function.
  2. Display the data part of the root (or current node).
  3. Traverse the right subtree by recursively calling the in-order function.
  4. Here is the result of pre-order traversal of above tree

                    10, 84, 20, 30, 40, 50, 60, 70
                5.Pictorial representation:

6. Program: We are using recursion as described above to programmatically traverse the tree.

1:       public void inOrder(TreeNode node){  
2:            if(node != null){  
3:                 inOrder(node.left);  
4:                 System.out.print(node.data+", ");  
5:                 inOrder(node.right);  
6:            }  
7:       }  

• Level Order:
• Display the data part of the root.
• Traverse the tree top to bottom and left to right
• Displaying each node, left node first.
• Here is the result of level order traversal of above tree

40,20,60,10,30,50,70,84

• Pictorial Representation:

• Program:
• Create a queue (linked list)
• Add root node to the queue.
• Loop the queue while it is not empty.
• Poll the first node from the queue.
• Print the data of extracted node.
• Add the left node to queue if it’s not empty
• Add the right node to queue if it’s not empty

1:       public void levelOrder(TreeNode node){  
2:            Queue<TreeNode> queue = new LinkedList<TreeNode>();  
3:            queue.add(node);  
4:            while(!queue.isEmpty()){  
5:                 TreeNode tempNode = queue.poll();  
6:                 System.out.print(tempNode.data+",");  
7:                 if(tempNode.left != null)  
8:                      queue.add(tempNode.left);  
9:                 if(tempNode.right != null)  
10:                      queue.add(tempNode.right);  
11:            }  
12:       }  

• Reverse Level Order:
• Display the data part of the bottom first node.
• Traverse the tree bottom to top and left to right
• Displaying each node, left node first.
• Here is the result of reverse level order traversal of above tree

84, 10, 30, 50, 70, 20, 60, 40

• Pictorial Representation:

• Program:
• Create a queue (linked list)
• Create a Stack.
• Add root node to the queue.
• Loop the queue while it is not empty.
• Poll the first node from the queue.
• Add the extracted node to stack.
• Add the right node to queue if it’s not empty
• Add the left node to queue if it’s not empty
• Now stack is full with node in level order (to-bottom, right-left). But stack performs First-In-Last-Out (FILO).
• Loop the stack while it is not empty
• Pop the first node out of stack and print its data element.

1:       public void reverseLevelOrder(TreeNode node){  
2:            Queue<TreeNode> queue = new LinkedList<TreeNode>();  
3:            Stack<TreeNode> stack = new Stack<TreeNode>();  
4:            queue.add(node);  
5:            while(!queue.isEmpty()){  
6:                 TreeNode tempNode = queue.poll();  
7:                 if(tempNode.right != null)  
8:                      queue.add(tempNode.right);  
9:                 if(tempNode.left != null)  
10:                      queue.add(tempNode.left);  
11:                 stack.add(tempNode);  
12:            }  
13:            while(!stack.isEmpty()){  
14:                 System.out.print(stack.pop().data+",");  
15:            }  
16:       }  

Junit Test Class to test all traversal techniques: 

1:  package com.research.tree;  
2:  import org.junit.Before;  
3:  import org.junit.Test;  
4:  public class BinaryTest {  
5:       TreeNode rootNode;  
6:       @Before  
7:       public void setUp(){  
8:            rootNode=new TreeNode(40);   
9:            TreeNode node20=new TreeNode(20);   
10:            TreeNode node10=new TreeNode(10);   
11:            TreeNode node30=new TreeNode(30);   
12:            TreeNode node60=new TreeNode(60);   
13:            TreeNode node50=new TreeNode(50);   
14:            TreeNode node70=new TreeNode(70);  
15:            TreeNode node84=new TreeNode(84);   
16:            rootNode.left=node20;   
17:            rootNode.right=node60;   
18:            node20.left=node10;   
19:            node20.right=node30;   
20:            node60.left=node50;   
21:            node60.right=node70;   
22:            node10.right = node84;  
23:       }  
24:       @Test  
25:       public void testPreOrder(){  
26:            BinaryTree bTree = new BinaryTree();  
27:            bTree.preOrder(rootNode);  
28:       }  
29:       @Test  
30:       public void testPostOrder(){  
31:            BinaryTree bTree = new BinaryTree();  
32:            bTree.postOrder(rootNode);  
33:       }  
34:       @Test  
35:       public void testInOrder(){  
36:            BinaryTree bTree = new BinaryTree();  
37:            bTree.inOrder(rootNode);  
38:       }  
39:       @Test  
40:       public void testLevelOrder(){  
41:            BinaryTree bTree = new BinaryTree();  
42:            bTree.levelOrder(rootNode);  
43:       }  
44:       @Test  
45:       public void testReverseLevelOrder(){  
46:            BinaryTree bTree = new BinaryTree();  
47:            bTree.reverseLevelOrder(rootNode);  
48:       }  
49:       @Test  
50:       public void testSpiralOrZigzagLevelOrder(){  
51:            BinaryTree bTree = new BinaryTree();  
52:            bTree.spiralOrZigzagLevelOrder(rootNode);  
53:       }  
54:  }