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

Given a sorted array, find k in least possible time in Java

Given a sorted array and a value k, write a program to find whether that number is present in that array or not.

The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.

This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.

Leave some comments if you have anything to say.

Cheers!
Braga

Queue using Stack in Java

A Queue can constructed with its underlying data structure being a stack. Typically, we will need two Stacks one for enqueue and the other for dequeue.

During every enqueue() operation over a queue, we will keep pushing value to a first stack, lets say stack1.

During every dequeue() operation, we will have to simply pop an element from stack2 if stack2 is not empty. If stack2 is empty, we will need to pop all elements from stack1 one by one and push it to stack2. And then pop an element from stack2.

Take for example, I am inserting elements from 1 to 6 to a queue. This is how the following queue and the corresponding stack will look like,

Then trying a dequeue() operation will try to immediately pop values from stack 2.

So, it will pop all values from stack1 and push them to stack2 as follows,

Now the dequeue() operation shall be performed with ease since stack2 is not empty.

Finally, more enqueue will add or keep pushing values to the stack.

Following is the Java code. Note, I have not comprehensively covered the entire methods in a Queue, but this should be well more than enough.



And a test class for this with output


Cheers!
Braga

Linked List : Given a pointer to any node, delete the node pointed by the pointer

Given a linked list like this,

Given a pointer to any node, delete the node pointed by the pointer. Note: no head pointer is given.

Solution:

Assume a pointer to p3, lets call it to 'p'. Since only pointer to current node is provided, there is no way to delete the current node from the list. But instead of deleting the current node, we can just move the next node data to current node and delete the next node. The algorithm can be explained simply as,

Cheers!!
Jack

Trie data structure - In C++

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Having had a comprehensive coverage of the TRIE data structure in Java, me and my roommate thought it would achieve completion if we have the same implemented in C++. Don't get carried away by the length of the code. Its as simple and easy as the equivalent one in Java. You may go through the comprehensive tutorial here. Trust me, it takes only 10 minutes!!.

Please feel free to ask any questions if you face difficulties in understanding any part of the resource. I would respond to you immediately.


Demonstration of trie operations

Cheers!!
Jack.

Stack Implementation in C++ through an array

Stack is one of the important data structures that every computer programmer should be aware of. It follows the simple LIFO (Last In First Out) principle. Implementation of stack can be done in many ways. One of the simplest way is using Arrays. Here an array is initialized to a maximum value first, lets call it capacity. As and when we push elements onto the array, its size will get increased. When the size reaches the capacity, we should ideally double the array size. But in the code given below I am not doing that.

Cheers!!
Bragaadeesh.

TRIE data structure Part 6 : A Sample UI

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Lets have a look at a sample application in Swing. We load the TRIE data structure using a dictionary word list. And using the application we can perform a search. This application is a very much prototypical just to check the insert() and search() operations.

Input file : words.txt

Sample Application

There are two possible outcomes to our search criteria, one true and another false. The following is the dialog shown when a word "article" is entered.

And when a word something like "dasdsa" is entered the following dialog is shown.

The Java code for the Trie Loader,

package dsa.tries;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class TrieLoader {
 
 public static Trie trieDSA;

 public static void main(String[] args) {
  TrieLoader trieLoader = new TrieLoader();
  trieLoader.load();
  new TrieTestFrame();
 }
 
 public void load(){
  trieDSA = new Trie();
  BufferedReader br = null;
  try {
   br = new BufferedReader(new FileReader(new File("src/properties/words.txt")));
   String eachLine = null;
   while((eachLine=br.readLine())!=null){
    trieDSA.insert(eachLine);
   }
  } catch (Exception e) {
   e.printStackTrace();
  } finally{
   if(br!=null){
    try {
     br.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
  }
 }
}

The TrieTestFrame,

package dsa.tries;

import java.awt.Dimension;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;

public class TrieTestFrame extends JFrame {

 private static final long serialVersionUID = 1L;
 
 private JPanel basePanel = new JPanel();
 private JTextField textField = new JTextField(20);
 private JButton button = new JButton("Check");

 public TrieTestFrame(){
  designUI();
 }
 
 private void designUI(){
  this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  this.setTitle("TRIE Test");
  
  button.addActionListener(new ActionListener() {
   @Override
   public void actionPerformed(ActionEvent e) {
    if(TrieLoader.trieDSA.search(textField.getText())){
     JOptionPane.showMessageDialog(basePanel, "The word you entered exist!!");
    }else{
     JOptionPane.showMessageDialog(basePanel, "The word you entered does not exist!!","Error",JOptionPane.ERROR_MESSAGE);
    }
   }
  });
  
  basePanel.add(textField);
  basePanel.add(button);
  
  add(basePanel);
  
  this.setSize(400,100);
  
  Toolkit tk = Toolkit.getDefaultToolkit();
     Dimension screenSize = tk.getScreenSize();
     int screenHeight = screenSize.height;
     int screenWidth = screenSize.width;
     setLocation(screenWidth / 2 - 200, screenHeight / 2 - 50);
  
  this.setVisible(true);
 }
}

For the Node and Trie class please click here.

Cheers,
Bragaadeesh.

TRIE data structure Part 5 : Complexity Analysis

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Now that we've seen the basic operations on how to work with a TRIE, we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity.

INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings. For every Node in the TRIE we had something called as Collection where the Collection can be either a Set or a List. If we choose Set, the order of whatever operation we perform over that will be in O(1) time, whereas if we use a LinkedList the number of comparisons at worst will be 26 (the number of alphabets). So for moving from one node to another, there will be at least 26 comparisons will be required at each step. 

Having these in mind, for inserting a word of length 'k' we need (k * 26) comparisons. By Applying the Big O notation it becomes O(k) which will be again O(1). Thus insert operations are performed in constant time irrespective of the length of the input string (this might look lik an understatement, but if we make the length of the input string a worst case maximum, this sentence holds true).

Same holds true for the search operation as well. The search operation exactly performs the way the insert does and its order is O(k*26) = O(1).

TRIE data structure Part 4 : The SEARCH Algorithm

• 1
• 2
• 3
• 4
• 5
• 6
• 7

In the previous section we saw how to insert string into TRIE. In this section, we shall see how to perform a search in the TRIE when a string or key is passed.

Consider the following TRIE as usual.

The search alogirthm involves the following steps

1. For each character in the string, see if there is a child node with that character as the content.
2. If that character does not exist, return false
3. If that character exist, repeat step 1.
4. Do the above steps until the end of string is reached. 
5. When end of string is reached and if the marker of the current Node is set to true, return true, else return false.

Using the above algorithm, lets perform a search for the key "do".

1. See whether "d" is present in the current node's children. Yes its present, so set the current node to child node which is having character "d".
2. See whether "o" is present in the current node's children. Yes its present, so set the current node to child node which is having character "o".
3. Since "o" is the end of the word, see whether marker is set to true or false. Marker is set to false which means that "do" is not registered as a word in the TRIE. So, return false.

Using the same algorithm, lets perform a search for the key "ball"

1. See whether "b" is present in the current node's children. Yes its present, so set the current node to child node which is having character "b".
2. See whether "a" is present in the current node's children. Yes its present, so set the current node to child node which is having character "a".
3. See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
4. See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
5. Since "l" is the end of the word, see whether marker is set to true or false. Marker is set to true which means that "ball" is registered as a word in the TRIE. So, return true

public boolean search(String s){
  Node current = root;
  while(current != null){
   for(int i=0;i<s.length();i++){    
    if(current.subNode(s.charAt(i)) == null)
     return false;
    else
     current = current.subNode(s.charAt(i));
   }
   /* 
    * This means that a string exists, but make sure its
    * a word by checking its 'marker' flag
    */
   if (current.marker == true)
    return true;
   else
    return false;
  }
  return false; 
 }

The above java code does the search operation in the TRIE data structure. We shall look more into the running time and efficiency of TRIE in the next part.

Cheers,
Bragaadeesh.

TRIE data structure Part 3 : The INSERT Algorithm

• 1
• 2
• 3
• 4
• 5
• 6
• 7

In this section we shall see how the insert() method on the TRIE data structure works. We shall take a specific case and analyze it with pictorial representation.

Before we begin, assume we already have an existing TRIE as shown below.

Lets see the steps on how to insert a word "bate". Any insertion would ideally be following the below algorithm.

1. If the input string length is zero, then set the marker for the root node to be true.
2. If the input string length is greater than zero, repeat steps 3 and 4 for each character
3. If the character is present in the child node of the current node, set the current node point to the child node.
4. If the character is not present in the child node, then insert a new node and set the current node to that newly inserted node.
5. Set the marker flag to true when the end character is reached.

Now if you go through the already written code for this, you can have a better understanding by comparing it with the above algorithm.

public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 } 

Now lets see how the word "bate" is getting inserted. Since the word "bate" is having length greater than zero, we can start inspecting each word.

• See whether "b" is present in the current node's children (which is root). Yes its present, so set the current node to the child node which is having the character "b".
• See whether "a" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "a".
• See whether "t" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "t".
• See whether "e" is present in the current node's children. No, its not present, so create a new node with character set to "e". Since "e" is the end of the word, set the marker flag to true.

The above picture shows how the word "bate" is inserted into the existing TRIE data structure. This example clearly shows how the insertion in a TRIE happens.
We shall take a look on the Search operation in the next part.

Cheers,
Bragaadeesh.

TRIE data structure Part 2 : Node and TRIE class in Java

• 1
• 2
• 3
• 4
• 5
• 6
• 7

In the first part of the TRIE ADT, we saw the basics of the TRIE data structure. In this section, lets get our hands dirty by directly looking at the TRIE data structure implemented in Java.

We already saw the Node structure of the TRIE ADT had a content (char), a marker (boolean) and collection of child nodes (Collection of Node). It now has one more method called as subNode(char). This method takes a character as argument would return the child node of that character type should that be present.

package dsa.tries;

import java.util.Collection;
import java.util.LinkedList;

/**
 * @author Braga
 */
public class Node {
 char content;
 boolean marker; 
 Collection<Node> child;
 
 public Node(char c){
  child = new LinkedList<Node>();
  marker = false;
  content = c;
 }
 
 public Node subNode(char c){
  if(child!=null){
   for(Node eachChild:child){
    if(eachChild.content == c){
     return eachChild;
    }
   }
  }
  return null;
 }
}

Now that we've defined our Node, lets go ahead and look at the code for the TRIE class. Fortunately, the TRIE datastructure is insanely simple to implement since it has two major methods insert() and search(). Lets look at the elementary implementation of both these methods.

package dsa.tries;

public class Trie{
 private Node root;

 public Trie(){
  root = new Node(' '); 
 }

 public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 }

 public boolean search(String s){
  Node current = root;
  while(current != null){
   for(int i=0;i<s.length();i++){    
    if(current.subNode(s.charAt(i)) == null)
     return false;
    else
     current = current.subNode(s.charAt(i));
   }
   /* 
    * This means that a string exists, but make sure its
    * a word by checking its 'marker' flag
    */
   if (current.marker == true)
    return true;
   else
    return false;
  }
  return false; 
 }
}

We shall look into the detailed working of the insert() and search() methods in separate posts, but I will tell you the gist of both those methods here. The insert() methods adds a new words to the already existing TRIE data structure. The search() method would return true or false based on whether the search string we specified exist or not.

Take a quick look at the java code above because we are going to use this in the posts that follow.

Cheers,
Bragaadeesh.

TRIE data structure Part 1: The TRIE ADT in Java

• 1
• 2
• 3
• 4
• 5
• 6
• 7

TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve. TRIE (pronounced as 'try') has a wide variety of applications in

• Spell checking
• Data compression
• Computational biology
• Routing table for IP addresses
• Storing/Querying XML documents etc.,

We shall see how to construct a basic TRIE data structure in Java.

The main abstract methods of the TRIE ADT are,

public void insert(String s);
public boolean search(String s);

In this data-structure, each node holds a character instead of a String. Each node has something called as 'marker' to mark the end of a word. And each node has a Collection of child nodes. This Collection can be either a Set or a List based on the speed vs space criterion.

The basic element - Node of a TRIE data structure looks like this,

char content;
boolean marker;
Collection<Node> child;

A TRIE tree would typically look like the following

The above TRIE is constructed by inserting the words ball, bat, doll, dork, do, dorm, send, sense. The markers are denoted on the Node using a red star(*). We shall look into more about the TRIE data structure in depth in the next post.

Reverse a Singly Linked List Recursively in Java

We have already seen how to reverse a singly linked list with illustrative pictures. Now lets see how we can do it recursively. In the previous problem we did it iteratively, now we shall do it recursively.
To attack any problem in a recursive approach, we need to be very clear about the end/boundary conditions. For a linked list, reverse of a null list or reverse of list of size 1 is going to be the same.
Reverse of a linked list of size x will be the reverse of the 'next' element followed by first.
A picture means a thousand words. So, here is what happens internally.

Now for the comprehensive Java code (reference for SinglyLinkedList implementation can be found here)


Cheers,
Bragaadeesh.

Stack using Linked Lists in Java

Stack is a data structure that follows the simple FILO (First In, Last out) or LIFO (Last In, First Out) rule. Imagine a real world stack where you arrange Notebooks one over the other. The first notebook you insert will be at the bottom and that will come only at last. The implementation of stack can be done in many ways. We are going to see how to make use of a Singly Linked List to the use.
We can implement stack using a Linked List in the below shown ways. One is to have the END node on top and other is to have the START node at the top. If we recollect the singly linked list data structure, insertAtFirst() is an operation which can be done in O(1) time and insertAtLast() will take O(n) time (because we need to traverse till the last node). So, we can make use of the second method to use stack using linkedlists.

The three methods that stands out for a stack are pop(), push() and peek().
push() - push elements into a stack. We will use the insertAtFirst() method of LinkedList. Throws StackOverflowException when the stack is full.
pop() - remove and returns the top element from a stack. We will use the removeAtFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.
peek() - return the top element from the stack without removing it. We will use the getFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.

The java code for this looks very simpler. We will make use of the existing SinglyLinkedList class that we have used before.

package dsa.stack;

import dsa.linkedlist.SinglyLinkedList;

public class Stack<E> extends SinglyLinkedList<E>{
 
 public static final int MAX_STACK_SIZE = 100;
 
 public E pop() throws StackEmptyException{
  if(this.size()==0){
   throw new StackEmptyException();
  }
  return this.removeAtFirst();
 }
 
 public E peek() throws StackEmptyException{
  if(this.size()==0){
   throw new StackEmptyException();
  }
  return this.getFirst().data;
 }
 
 public void push(E data) throws StackOverflowException{
  if(this.size()>MAX_STACK_SIZE){
   throw new StackOverflowException();
  }
  this.insertAtFirst(data);
 }
 
 public static void main(String args[]){
  Stack<Integer> stack = new Stack<Integer>();
  try{
   System.out.println("Pushing 1, 2, 3, 4, 5");
   stack.push(1);
   stack.push(2);
   stack.push(3);
   stack.push(4);
   stack.push(5);
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Peek once : "+stack.peek());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
  }catch(StackEmptyException e){
   System.out.println(e.getMessage());
  }catch(StackOverflowException e){ 
   System.out.println(e.getMessage());
  }
 }
}
/*
SAMPLE OUTPUT:
Pushing 1, 2, 3, 4, 5
Pop once  : 5
Peek once : 4
Pop once  : 4
Pop once  : 3
Pop once  : 2
Pop once  : 1
Stack is empty!
*/

package dsa.stack;

public class StackEmptyException extends Exception{
 public StackEmptyException(){
  super("Stack is empty!");
 }
}

package dsa.stack;

public class StackOverflowException extends Exception{
 public StackOverflowException(){
  super("Stack Overflown");
 }
}

Cheers,
Bragaadeesh.

Find kth node from the last in a singly linked list without using counter

The objective for this program is to find the kth node from the last without actually finding the size of the singly linked list.
For this problem, we need to have two pointers, lets call them FAR and NEAR. We need to initialize them by pointing them to the start. After doing that, move the FAR pointer 'k-1' times ahead. After moving that run a loop until FAR becomes null, amidst that increment both FAR and NEAR pointers.
The below picture shown is done for k=3. In step1, we are moving the pointer k-1=2 times. After that by moving parallely FAR and NEAR pointers, we can find the kth element from the last by getting the data from NEAR pointer.

The Java code for this simple program is given below. To try the below program please copy this class as well.

package dsa.linkedlist;

public class FindKthElementFromLast {
 public static void main(String args[]){
  FindKthElementFromLast kthFromLastFinder = new FindKthElementFromLast();
  SinglyLinkedList<Integer> originalList = kthFromLastFinder.getLabRatList(8);
  System.out.println("Original List : "+originalList.toString());
  kthFromLastFinder.findFromLast(originalList, 3);
 }
 
 private void findFromLast(SinglyLinkedList<Integer> singlyLinkedList, int k) {
  Node far, near;
  //initialize far and near pointers
  far = near = singlyLinkedList.start;
  //Move the far pointer k times from the starting position
  System.out.print("kth node from last for k = "+k+" is ");
  while((k--)!=0){
   far = far.next;
  }
  while(far!=null){
   near = near.next;
   far = far.next;
  }
  System.out.println(near.data);
 }

 private SinglyLinkedList<Integer> getLabRatList(int count){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=1;i<=count;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
}
//SAMPLE OUTPUT
//Original List : 1, 2, 3, 4, 5, 6, 7, 8
//kth node from last for k = 3 is 6

Cheers,
Bragaadeesh.

Least Common Ancestor without using a parent node in java

We already saw how to find the Least Common Ancestor for a binary tree. The problem gets a bit tricky when the node structure is like this.

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

If you look at the above structure, there are no parent nodes and the given tree is not a Binary Search Tree which makes the problem all the more complicated.
To attack this problem we need to follow the below steps.

1. Find the path of the first node using in-order traversal - Cost: O(n)
2. Find the path of the second node using in-order traversal - Cost: O(n)
3. Put the nodes of the first path in a set - Cost: O(logn)
4. For each node in the second path check if it exists in the first path. The matching one would be the Least Common Ancestor - Cost: O(logn)

The total cost for this program would be - O(n) + O(n) + O(logn) + O(logn) = O(n).

Now for the java code. I am going to use the Trace Algorithm from the previous post for this solution to make life easier. Hope you were able to learn something.

package dsa.tree;

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

/**
 * Program to find the Least Common Ancestor without
 * for a Binary Tree (Not a BST). The Node does not have
 * a parent pointer. The direction of the tree is one sided
 * @author Braga
 *
 */
public class LCSBinaryTree {
 private Node n1,n2;
 
 public static void main(String args[]){
  LCSBinaryTree nodeFinder = new LCSBinaryTree();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  if(commonParent == null){
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is null");
  }else{
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is "+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(76);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  TracePath pathTracer = new TracePath();
  
  /**
   * If either of the nodes is root, then there is no common
   * parent
   */
  if(node1.equals(t.getRoot()) || node2.equals(t.getRoot())){
   return null;
  }
  //Using the path tracer, find the path of two nodes in 2*O(n) time.
  Stack<Node> path1 = pathTracer.trace(t, node1);
  Stack<Node> path2 = pathTracer.trace(t, node2);
  
  //All that is left to do is to find the common parent now.
  Set<Node> firstPath = new HashSet<Node>();
  for(Node iNode:path1){
   firstPath.add(iNode);
  }
  while(!path2.isEmpty()){
   Node currentNode = path2.pop();
   if(firstPath.contains(currentNode)){
    if(!path2.isEmpty() && firstPath.contains(currentNode = path2.peek())){
     return path2.peek();
    }
    return currentNode;
   }
  }
  return null;
 }
}
//SAMPLE OUTPUTS
//Common Parent for 887 and 334 is 43
//Common Parent for 43 and 334 is null
//Common Parent for 6 and 334 is 43
//Common Parent for 76 and 334 is 46

Cheers,
Bragaadeesh.

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.

Program to find center of a singly linked list in java

This is a very common data structure problem, to find the center of a singly linked list. And the following is the famous solution. I have tried to give a comprehensive code coverage for this problem. The list count can either be odd or even. If its odd, we have only one value as the center and two for even case. I have covered both in the following code. Please do take a look at the SinglyLinkedList class for this program for reference.
This is how it works, there will be two pointers, one jumping once and another one jumping twice. When the double jumper ends/terminates, the single jump fellow's data would be the center.

package dsa.linkedlist;

public class FindCenterOfAList {
 public static void main(String args[]){
  FindCenterOfAList ratList = new FindCenterOfAList();
  ratList.test(10);//TEST FOR EVEN
  ratList.test(17);//TEST FOR ODD
  ratList.test(1);//TEST FOR SINGLE
  ratList.test(0);//TEST FOR ZERO OR LESS
 }
 
 public int[] getMidItem(SinglyLinkedList<Integer> listToCheck){
  Node<Integer> singleJump = listToCheck.start;
  Node<Integer> doubleJump = listToCheck.start;
  
  while(doubleJump.next!=null && doubleJump.next.next!=null){
   singleJump = singleJump.next;
   doubleJump = doubleJump.next.next;
  }
  
  int[] midItem = null;
  
  if(doubleJump.next == null){
   midItem = new int[1];
   midItem[0] = singleJump.data;
  }else if(doubleJump.next.next == null){
   midItem = new int[2];
   midItem[0] = singleJump.data;
   midItem[1] = singleJump.next.data;
  }
  
  return midItem;
 }
 
 private void test(int sampleSize){
  if(sampleSize<1){
   System.out.println("List is empty!");
   return;
  }
  SinglyLinkedList<Integer> randomList = giveMeAList(sampleSize);
  System.out.print("For list : ");stringify(randomList);
  int[] midItem = getMidItem(randomList);
  if(midItem.length == 1){
   System.out.println("Middle Item : "+midItem[0]);
  }else if(midItem.length == 2){
   System.out.println("Middle Items : "+midItem[0]+", "+midItem[1]);
  }
  System.out.println();
  
 }
 
 private SinglyLinkedList<Integer> giveMeAList(int length){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=1;i<=length;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
 
 private void stringify(SinglyLinkedList<Integer> ratList) {
  for(int i=0;i<ratList.size;i++){
   System.out.print(ratList.getNodeAt(i).data+" ");
  }
  System.out.println();
 }
}
/*
-------OUTPUT--------
For list : 1 2 3 4 5 6 7 8 9 10 
Middle Items : 5, 6

For list : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
Middle Item : 9

For list : 1 
Middle Item : 1

List is empty!
*/

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.