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

Comparator Example

How to compare a bean class and sort it accordingly?

We will use Comparator Interface for this.

  1)      We will create a bean class which will have two properties i.e. name,age. This class will also override the toString method for presentation purpose.

package com.javabreed.example.comparator;

public class PersonBean {

       private String name;

       private int age;

      

       public String getName() {

              return name;

       }

       public void setName(String name) {

              this.name = name;

       }

       public int getAge() {

              return age;

       }

       public void setAge(int age) {

              this.age = age;

       }

       @Override

       public String toString() {

              return "PersonBean [name=" + name + ", age=" + age + "]";

       }

      

      

}

  2)      Then we will create a NameComparator class by implementing Comparator interface. This class will have overridden compareTo method to compare the names property of above given bean objects.

package com.javabreed.example.comparator;

import java.util.Comparator;

public class NameComparator implements Comparator<PersonBean> {

       @Override

       public int compare(PersonBean arg0, PersonBean arg1) {

              return arg0.getName().compareTo(arg1.getName());

       }

}

  3)      Similarly we will create a AgeComparator class by implementing Comparator interface. This class will have overridden compare method to compare the age property of above given bean objects.  This comparison will work in ascending order, just flip these ‘>’ or ‘<’ signs to get the results in descending order.

package com.javabreed.example.comparator;

import java.util.Comparator;

public class AgeComparator implements Comparator<PersonBean>{

       public int compare(PersonBean o1, PersonBean o2) {

              int age1=o1.getAge();

       int age2=o2.getAge();

       if(age1 < age2)    // Will give sorted list in ascending order. Flip the '<' to '>' and you can get  

            return -1;     // results in descending order.

        else if(age1 > age2)

            return 1;

        else

            return 0;

       }

}

  4)      Finally a main class to show the results. This class will create a list of PersonBean objects. First it’ll print the unsorted list. Program will then sort this list by name, and then by age.

 package com.javabreed.example.comparator;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Collections;

import java.util.List;

public class ComparatorMain {

      

       public static void main(String args[]){

              List<PersonBean> list= new ArrayList<PersonBean>();

             

              PersonBean personBean= new PersonBean();  //1st Person

              personBean.setName("Surya");

              personBean.setAge(20);

              list.add(personBean);

             

              personBean= new PersonBean();  //2nd Person

              personBean.setName("Ramya");

              personBean.setAge(25);

              list.add(personBean);

             

              personBean= new PersonBean();  //3rd Person

              personBean.setName("Anil");

              personBean.setAge(23);

              list.add(personBean);

             

              System.out.println("Unsorted List "+list);

              Collections.sort(list,new NameComparator());

              System.out.println("Sorted by name List "+list);

              Collections.sort(list,new AgeComparator());

              System.out.println("Sorted by age List "+list);

       }

}

 Try this and let me know if you have any questions.