Reconstruct a binary tree given its Inorder and Preorder traversals in Java

This is one of the interesting problems that I encountered recently. Given two sequences one being an in-order traversed sequence and other being a pre-ordered traversed sequence, a binary tree has to be reconstructed out of it.

This is theoretically possible. This problem can be cracked if we form a common pattern between these two traversed values. In a pre-order traversal, the root element will always be the first element. This element when searched in an in-order traversal will have all elements to the left on the left side of the array and all elements to the right on the right side of the array.

Applying this solution recursively will give the binary tree for us. I have included a Swing UI so as to visualize the output easily.

Example,
Pre Order Sequence = A B D E C F G H I
In Order Sequence = D B E A F C H G I

I tweaked a bit from this source for UI.

The Node structure

The code for UI

Hope you learnt something today along with me.

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

Given an array find any pair that sums up into a number

This problem is quite largely discussed and is very famous for its various ways to attack. This can be constrained in time and in space. The most primitive way of attacking this problem would yield an solution that runs in O(n²) time.
Let me define the problem clearly. Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X. Only one pair would be enough.
Lets see how we can find the solution for this in O(n) using a HashSet. Yes, HashSet is a costly data structure to use, but lets consider this primitive just due to the linear order it provides.

We shall improvise on this problem in space domain using fancy sorts and those we shall see in the coming posts.

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

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.

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 Trees in Java

One of the coolest data structures that is both highly efficient and very simple is a Binary Tree. Binary Tree is a data structure where a there will be a node having at most two child nodes.

Lets briefly define the concepts of a binary tree and lets take look at a working Java program in the future posts. Binary Tree has three pointers, one pointing to the left child, one pointing to the right child and one pointer to the parent. These are the terms we use with respect to a binary tree.

• Root - The uppermost node in a binary tree. The parent node is always null for a root or we can say Root does not have a parent.
• Child - A child is a sub-node to a parent node. A child can be either a left child or a right child
• Leaf - A node which does not have any right or left nodes to it.
• Node - constitutes to an element of a tree which has three pointers one to parent, one to right child and one to left child. And it has a place holder to store the data as well.
  

There are more jargons available with regard to a binary tree but as of now these terms are sufficient.

One of the most common misunderstanding that many have is to tell the definition of a "Binary search tree" when asked for a "Binary tree". They are not the same!!. Although we can say binary search tree is a form of binary tree with some condition. All Binary search trees are Binary trees and not vice versa!!!!

If asked to write a binary tree structure in Java, the following code would be more than sufficient. Note: This is just a raw structure.

public class BinaryTree{
 
 class Node {
  Node left;
  Node right;
  Node parent;
  int data;
 }
 
 private Node root;

}

More trees to come in the following posts.
Cheers,
Bragaadeesh.

Quick Sort in Java

Quick sort is one of the coolest algorithms available in sorting and its performance is measured most of the time in O(nlogn), although the worst case sorting times of bubble sort and this are equal.
Inspite its worst case time, this always performs superiorly when the input is completely shuffled/randomized. This is one of the modest sorts available :).

Quick sort is an example of in-place sort. No extra space is needed as in merge sort where we have to use one full extra array to hold all the merged values. The only space that quick sort uses may be the counter variables and the extra space required for swapping.

Below is a pictorial representation of how this quick sort works,

I ran this sort for a well randomized data of million elements again and again and it beats the Merge sort hands down having a 75% quicker speed. Its always advisable to have shuffle the data upfront before running this algorithm.
Here is the source code for the same,

package dsa.sorting;

/**
 * A wonderful inplace sorting technique
 * @author Braga
 */
public class QuickSort {
 
 public static int SIZE = 1000000;

 public int[] sort(int[] input) {
  quickSort(input, 0, input.length-1);
  return input;
 }
 
 public static void main(String args[]){
  int[] a = new int[SIZE];
  for(int i=0;i<SIZE;i++){
   a[i] = (int)(Math.random()*SIZE);
  }
  QuickSort mNew = new QuickSort();
  long start = System.currentTimeMillis();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a million elements : "+(end-start)+" milliseconds");
 }
 
 public void print(int[] inputData) {
  for(int i:inputData){
   System.out.print(i+" ");
  }
  System.out.println();
 }
 
 private void quickSort(int arr[], int left, int right) {
  int index = partition(arr, left, right);
  if (left < index - 1)
   quickSort(arr, left, index - 1);
  if (index < right)
   quickSort(arr, index, right);
 }
 
 private int partition(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  while (i <= j) {
   while (arr[i] < pivot)
    i++;
   while (arr[j] > pivot)
    j--;
   if (i <= j) {
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
   }
  }
  return i;
 }
}
//Time taken to sort a million elements : 156 milliseconds

Pros:
1) Efficient average case compared to any algorithm.
2) Recursive definition and popularity because of its high efficiency.

Cons:
1) Worst case scenario sucks.

As we discussed the worst case can be easily overcome by deliberately shuffling the input. I would rate quick sort as one of the best techniques available in sorting till date.

More sorting methods yet to come.
Cheers,
Bragaadeesh.

An inefficient implementation of Merge Sort in Java

It is not always enough just to understand how an algorithm works and do some theoretical calculations on the running time. We need to go to that extra step to actually implement for ourselves and check the performance. That is the only way to understand it piece by piece and that is the way that it remains in you forever.
This scenario happened to me with merge sort algorithm. I learnt how the algorithm actually worked and even implemented it in java. But found out that the performance of it was worse than a simple bubble sort!! I followed all the steps that was given in the 'theoretical' portion of the algorithm. But still my output was worse.
First take a brief look at the code

package dsa.sorting;

import java.util.Arrays;


public class MergeSort{

public static int SIZE = 100000;

public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;i<SIZE;i++){
a[i] = (int)(Math.random()*SIZE);
}
long start = System.currentTimeMillis();
MergeSort mSort = new MergeSort();
mSort.sort(a);
long end = System.currentTimeMillis();
System.out.println("Time taken to sort a 100,000 elements : "+(end-start)+" milliseconds");
}

public int[] sort(int[] input) {
if(input.length<=1){
return input;
}
int[] left, right, result;

int mid = input.length/2;

left = Arrays.copyOfRange(input, 0, mid);
right = Arrays.copyOfRange(input,mid,input.length);

left = sort(left);
right = sort(right);

result = merge(left,right);

return result;
}

public int[] merge(int[] left, int[] right){
int[] result = new int[left.length+right.length];
int indexOfResult = 0;
while(left.length>0 && right.length>0){
if(left[0]<right[0]){
result[indexOfResult++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}else{
result[indexOfResult++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
if(left.length>0){
for(int i=0;i<left.length;i++){
result[indexOfResult++] = left[i];
}
}else{
for(int i=0;i<right.length;i++){
result[indexOfResult++] = right[i];
}
}
return result;
}
}
//Time taken to sort a 100,000 elements : 13401 milliseconds

After seeing the output, i kind of went nuts. I was clueless at the start on why my program was performing this bad! Later I realized that I was using up resources like anything through the Array.copyOfRange() method! It is a raw array copy which is simply not acceptable both in space and in time aspect.
Space - because of the in-numerous arrays that are getting created and Time - because of the heavy copy operations.

Later i realized i can use indexes to manipulate on the algorithms and just use only one extra array to do all my operations!! That is when i arrived at this.
A lesson well learnt!

Cheers,
Bragaadeesh.