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:  }  

How to create a LinkedList in Java.

How to create a LinkedList in Java.

I am assuming that everyone knows what is linked list? Click here to know more about linked list. 

Functionality of this program:

1. Create a Node class which will represent the Singly Linked List.
   • Value at linked list node
   • Next Node
2. Singly Linked List Implementation Class
   • Head: First node of the linked list. Initial value is null.
   • Tail: Last node of the linked list. Initial value is null.
   • add Method: This method adds a node at the end of the linked list.
   • addAfter Method: adds a node after a given node.
   • deleteAfter Method: deletes a node after a given node.
   • deleteFront Method: deletes the head node which is also is the starting point of the linked list. After this method second node of the linked list becomes the head node.
   • reverse Method: revers the given linked list.
   • traverse Method: prints the full linked list.
3. Result of this program:

1:  package com.research.list.linkedlist;  
2:  public class Node<T> implements Comparable<T> {  
3:       private T value;  
4:       private Node<T> nextRef;  
5:       public T getValue() {  
6:            return value;  
7:       }  
8:       public void setValue(T value) {  
9:            this.value = value;  
10:       }  
11:       public Node<T> getNextRef() {  
12:            return nextRef;  
13:       }  
14:       public void setNextRef(Node<T> nextRef) {  
15:            this.nextRef = nextRef;  
16:       }  
17:       public int compareTo(T arg) {  
18:            if(arg == this.value){  
19:             return 0;  
20:           } else {  
21:             return 1;  
22:           }  
23:       }  
24:  }  

1:  package com.research.list.linkedlist.singly;  
2:  import org.springframework.stereotype.Component;  
3:  import com.research.list.linkedlist.Node;  
4:  public class SinglyLinkedListImpl<T> {  
5:       Node<T> head;  
6:       Node<T> tail;  
7:       public void add(T element){  
8:            Node<T> node = new Node<T>();  
9:            node.setValue(element);  
10:            if(head == null){  
11:                 head = node;  
12:                 tail = node;  
13:            } else {  
14:                 tail.setNextRef(node);  
15:                 tail = node;  
16:            }  
17:       }  
18:       public void addAfter(T element, T after){  
19:            Node<T> node = new Node<T>();  
20:            node.setValue(element);  
21:            Node<T> tmp = head;  
22:            Node<T> refNode = null;  
23:            while(true){  
24:                 if(tmp == null)  
25:                      break;  
26:                 if(tmp.compareTo(after) == 0){  
27:                      refNode=tmp;  
28:                      break;  
29:                 }  
30:                 tmp = tmp.getNextRef();  
31:            }  
32:            if(refNode != null){  
33:                 node.setNextRef(tmp.getNextRef());  
34:                 if(tmp.compareTo(tail.getValue()) == 0)  
35:                      tail=node;  
36:                 tmp.setNextRef(node);  
37:            }  
38:       }  
39:       public void deleteFront(){  
40:            if(head == null){  
41:                 System.out.println("UnderFlow");  
42:            } else{  
43:                 Node<T> tmp = head;  
44:                 head = tmp.getNextRef();  
45:                 if(head == null){  
46:                      tail = null;  
47:                 }  
48:            }  
49:       }  
50:       public void deleteAfter(T after){  
51:            Node<T> tmp = head;  
52:            Node<T> refNode = null;  
53:            while(true){  
54:                 if(tmp == null)  
55:                      break;  
56:                 if(tmp.compareTo(after) == 0){  
57:                      refNode=tmp;  
58:                      break;  
59:                 }  
60:                 tmp=tmp.getNextRef();  
61:            }  
62:            if(refNode != null){  
63:                 tmp = refNode.getNextRef();  
64:                 refNode.setNextRef(tmp.getNextRef());  
65:                 if(refNode.getNextRef() == null){  
66:                      tail = refNode;  
67:                 }  
68:            }  
69:       }  
70:       public void reverse(){  
71:            Node<T> currentNode = head;  
72:            Node<T> nextNode = null;  
73:            Node<T> previousNode = null;  
74:            while(currentNode != null){  
75:                 nextNode = currentNode.getNextRef();  
76:                 currentNode.setNextRef(previousNode);  
77:                 previousNode = currentNode;  
78:                 currentNode = nextNode;  
79:            }  
80:            head = previousNode;  
81:       }  
82:       public void traverse(){  
83:            Node<T> tmp = head;  
84:            while(true){  
85:                 if(tmp == null)  
86:                      break;  
87:                 System.out.print(tmp.getValue()+",");  
88:                 tmp=tmp.getNextRef();  
89:            }  
90:            System.out.println("");  
91:       }  
92:       public static void main(String[] args) {  
93:            SinglyLinkedListImpl<Integer> linkedList = new SinglyLinkedListImpl<Integer>();  
94:            linkedList.add(3);  
95:            linkedList.add(45);  
96:            linkedList.add(12);  
97:            linkedList.add(32);  
98:            linkedList.add(49);  
99:            linkedList.add(98);  
100:            linkedList.add(90);  
101:            linkedList.add(42);  
102:            linkedList.traverse(); // 1: Traverse - initial Linked List  
103:            linkedList.addAfter(21, 90);  
104:            linkedList.traverse(); // 2: Traverse - after adding 21 after 90  
105:            linkedList.addAfter(67, 42);  
106:            linkedList.traverse(); // 3: Traverse - after adding 67 after 42  
107:            linkedList.deleteAfter(49);  
108:            linkedList.traverse(); // 4: Traverse - after deleting number after 49  
109:            linkedList.deleteFront();  
110:            linkedList.traverse(); // 5: Traverse - after deleting front number from linked list  
111:            linkedList.reverse();  
112:            linkedList.traverse(); // 6: Traverse - after reversing the linked list  
113:       }  
114:  }