Tree Traversal in C++

We've already seen many implementations of tree and its uses in java. Lets look at a simple implementation of traversing on a tree in C++. Code has been given below which I think is quite self descriptive.

Regards,
Jack

Trace path of a node in a BINARY TREE in Java

The problem is simple. Given a node, we should be able to show the path from the root to that node in a BINARY TREE (NOT A BINARY SEARCH TREE). This solution would help us how to traverse through a binary tree. Here I am going to do an inorder traversal. More on traversals on a binary tree can be found here.
Consider the following binary tree, we can see the path to be found and the node supplied to find it. We will be provided with a tree, its root and the node to be found.

76 is the item that we need to find. Although the example looks like a BINARY SEARCH TREE, we are not going to use the binary search tree way to find 76. So, we would have no other way than doing either of inorder, post-order or pre-order traversals. 

To attack this problem,we maintain a stack. The stack will always maintain the path. Whenever we encounter the node to be found, we will stop our process and the path in the current stack will give the path to be found. The solution for this problem shown would be : 43,887,46,78,76

I was having problem in returning from the recursive method in a proper manner. Thanks to the help of stackoverflow.com  and its code gurus, I was redirected to the right path.

Now, for the Java code part,

package dsa.tree;

import java.util.Stack;

public class TracePath {
 private Node n1;
 private Stack<Node> mainStack = null;
 
 public static void main(String args[]){
  TracePath nodeFinder = new TracePath();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  trace(t,n1);
  for(Node iNode:mainStack){
   System.out.println(iNode.data);
  }
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(76);
  return bsTree;
 }
 
 public Stack<Node> trace(Tree t, Node node){
  mainStack = new Stack<Node>();
  trace(t.getRoot(),node);
  return mainStack;
 }
 
 private boolean trace(Node parent, Node node){
  mainStack.push(parent);
  if(node.equals(parent)){
   return true;
  }
  if(parent.left != null){
   if (trace(parent.left, node))
    return true;
  }
  if(parent.right!=null){
   if (trace(parent.right, node))
    return true;
  }
  mainStack.pop();
  return false;
 }
}

Find common parent in a binary search tree in Java

This is a very famous question that many already are aware of. But I wanted to give a comprehensive working program in java to implement this with illustration. Consider the following binary tree which infact is a binary search tree.

The idea is very simple. For the first node traverse up till you reach root, while doing so, put the nodes in a hash set. Then do the same for the second node ie, try to traverse towards the root. Amidst doing that search for the existence of this node in the hash set we already created for the first traversal.

The place where those two nodes matches will be the common node. For any two nodes in a tree, there will be at least one common node which will be the root. I have given two examples below. One having a node other than root as the common parent and the other with root as the common parent.

The green line shows the traversal of first node path. Red shows the second node's path. The intersection or the common parent is shown in a blue circle.

Now for the Java source.

package dsa.tree;

import java.util.HashSet;
import java.util.Set;

public class FindCommonNode {
 private Node n1,n2;
 
 public static void main(String args[]){
  FindCommonNode nodeFinder = new FindCommonNode();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  System.out.println("Common Parent : "+commonParent.data);
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(45);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  Set<Node> firstNodeAddrSet = new HashSet<Node>();
  //Traverse till root
  while(node1!=null){
   firstNodeAddrSet.add(node1);
   node1 = node1.parent;
  }
  while(!firstNodeAddrSet.contains(node2) && node2!=null){
   node2 = node2.parent;
  }
  return node2;
 }
}

The implementations for Tree and BinarySearchTree can be found here.

Cheers,
Bragaadeesh.

Traversals in a binary search tree in Java

Now that we have seen how a binary tree is structured and doing a search operation over the same, lets look at how we can traverse over that data structure. There are three types of traversals that can be done.

1. In-order traversal
2. Pre-order traversal
3. Post-order traversal

In-order traversal follows the route VISIT LEFT / VISIT ROOT / VISIT RIGHT. For a given binary tree, first visit the left most node and if no left node exists, visit the root and then visit the right. By this fashion traversal can be done. As a matter of fact, a simple In-order traversal in a binary search tree would give the sorted result! How cool is that!?

If you take a look at the above picture (yes, it looks a bit crowded, but you can track the numbers from 1 through twenty and the green ones are the values that we take), we start the process from the root and end up in the root. First search for the left most node. If there is none available take the immediate root and apply the same algorithm to the current node's right node. What i say may be a bit confusing but follow the numbers, you'l know.

Pre-order traversal follows the route VISIT ROOT / VISIT LEFT / VISIT RIGHT and the Post-order traversal follows the VISIT LEFT, VISIT RIGHT, VISIT ROOT.

For the above given example, the sequence that we get for various traversals is listed in the table below. You can cross-check it for yourself.

Order	Sequence
In-order	9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76
Pre-order	50, 17, 9, 14, 12, 23, 19, 76, 54, 72, 67
Post-order	12, 14, 9, 19, 23, 17, 67, 72, 54, 76, 50

In order traversal's application is clearly visible in this example (it gives a sorted list). Pre and post order traversals too have some powerful applications which we will look in the following posts.

Cheers,
Bragaadeesh.

Searching in a Binary Search Tree in Java

Now that we have a working version of a binary search tree fully implemented in Java, lets go a step ahead and start analyzing that piece of code.

Binary search tree is a data structure which has the following public methods exposed

public void add(int data);
public boolean search(int searchData);
public void printOrdered();

Ofcourse, the above three methods are not the only methods present in a binary search tree, but once these methods are understood and analyzed, understanding the rest of the binary tree should not be a big problem.

Adding elements to a binary tree : In the example program that I've written, I am using only integers as the node data to hold values and ofcourse you need something that is comparable to make binary search trees realistic (refer my previous post on comparable objects). While adding data to a binary search tree, we need to follow the simple rule - lesser should go left and greater then or equal should go to the right of the parent node. By taking a snap at the code, the add(int data) method internally calls a private method that does the job in recursion.

Searching elements in a tree : Searching elements in any data structure is a essential part that reflects the space and time complexity and Binary search tree is no exception. To search from a balanced binary search tree, it would take only O(logn) whereas the same is not so in case of an Array. The simple reason being, for arrays, we need to traverse the entire array sequentially in which the worst case would produce O(n). Consider the below example where in we need to search the element 5.

Whereas in a binary search, the depth count would simply provide the desired result.
Consider a situation in a balanced binary search tree of 7 elements, when the value given to search is at its leaf (which would be the worst case here). The example shown below is a balanced and a perfect binary search tree (which we would look into future posts). Assume the element we need to find is 5. First inspect the root (4), our value is greater, so go the right node, then inspect it (6), our value is lesser so go the left node, bingo! we found our result. This took only 2 comparisons of a tree of depth 2 whereas it look 7 comparisons in an array of length 7! Through this we can come to conclusion that binary trees perform search in O(logn) time.

The method printOrdered() is something we have to allocate time and look into a different post. As for now, lets convince ourselves that binary tree's search is powerful enough to perform the search operation in O(logn) time.
Rest, later. Cheers,
Bragaadeesh.

Binary Search Trees in Java

Now that we've seen how a binary tree is structured, lets take a look at one of the most common and powerful implementations - Binary Search Trees.
Binary Search trees are binary trees with some defined rules. Binary search trees can be formed only to nodes which are comparable. By Comparable, i mean which objects in real life that can be compared with each giving outputs as equal, greater or lesser. Numerals are the simplest example of comparables.
The rule of binary search tree follows that all the nodes that are lesser than the root will be on the left and the nodes that are greater than will be on the right. Equal valued nodes can come on either side.
Following is a simple illustration of a binary search tree formed using numerals

The following is a comprehensive Java code on how to construct and then manipulate from a binary tree.

The abstract Data Structure for Tree and the class Node.

package dsa.tree;

public interface Tree {
 public void add(int currentData);
 public Node search(int data);
}

package dsa.tree;

public  class Node {
 Node left;
 Node right;
 Node parent;
 int data;
}

package dsa.tree;

public class BinarySearchTree implements Tree{
 
 private Node root;
 
 public void add(int currentData){
  if(root == null){
   root = new Node();
   root.data = currentData;
   return;
  }
  add(currentData, root);
 }
 
 private void add(int currentData, Node position){
  if(currentData<position.data){
   if(position.left==null){
    position.left = new Node();
    position.left.data = currentData;
    position.left.parent = position;
    return;
   }
   add(currentData, position.left);
  }else{
   if(position.right==null){
    position.right = new Node();
    position.right.data = currentData;
    position.right.parent = position;
    return;
   }
   add(currentData, position.right);
  }
 }
 
 public Node search(int searchData){
  if(root == null){
   return null;
  }
  return search(searchData, root);
 }
 
 /*
  * O(log n) on average case
  */
 private Node search(int searchData, Node node){
  if(node.data == searchData){
   return node;
  }
  if(searchData < node.data){
   return search(searchData, node.left);
  }else{
   return search(searchData, node.right);
  }
 }
 
 public void printOrdered(){
  if(root == null){
   return;
  }
  printOrdered(root);
 }
 
 //DO A IN ORDER TRAVERSAL
 //VISIT LEFT
 //VISIT ROOT
 //VISIT RIGHT
 public void printOrdered(Node node){
  if(node.left != null){
   printOrdered(node.left);
  }
  System.out.println(node.data);
  if(node.right!=null){
   printOrdered(node.right);
  }
 }
 
 public void printValues(){
  print(root);
 }
 
 private void print(Node node){
  if(node == null){
   return;
  }else{
   print(node.left);
   print(node.right);
  }
 }
 
 public static void main(String args[]){
  BinarySearchTree bTree = new BinarySearchTree();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println(t);
   bTree.add(t);
  }
  bTree.printValues();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println("For i="+t+": "+bTree.search(t));
  }
  System.out.println();
  bTree.printOrdered();
 }
}

We shall discuss about the various features used in this program in the following post.

Bragaadeesh.