Category Archives: Binary Search Tree

Creating a balanced binary search tree from sorted array

Given a sorted array, how do we create binary search which height balanced.

For example the array [1,2,3,4,5] must be transformed to the following binary tree

                           3
                / 
               2    4
              /       
             1        5

We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.

How do we do it?
 

The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.

Here is the C++ code.

Binary-2Bsearch-2Btree

Finding the kth element in Binary search tree

Given a binary search tree, how do we find a kth smallest or kth largest element?
For example, given the following binary search tree.
Third largest element is 6
Second smallest element is 2
Fifth largest element is 5 and so on…

Solution:


We can solve this problem by modifying the the in-order traversal method of a binary tree. In addition to the root node, we can pass two more parameters one is K, and current count of the nodes visited as a reference parameter. When the current count reaches K we found the kth order element.

To find out the kth smallest element, we need to visit left sub-tree, then root and then the right sub-tree as usual. To find the kth largest element we need to do reverse in-order traversal i.e First visit right sub-tree, then root and then the left sub-tree.

Here is the C++ implementation. This includes the recursive and iteration versions of finding kth smallest and kth largest elements. The iterative version is simply the manual implementation of a recursion using a stack.

Finding the minimum and maximum elements in a binary seach tree

Given a binary search tree, how do we find the maximum and minimum elements in it?

For example in the given tree, the maximum element is 8 and the minimum element is 1.
This algorithm is based on the following simple observation.
In a Binary search tree, the minimum element always lies on the left most node and the maximum element always lies on the right most node.
Here is the simple implementation of this algorithm in C++.

Finding the height of the binary tree

Given a binary tree how to find the height of the tree. 
It is defined as the number of nodes in the longest path from root to any leaf.

 We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the below tree has a height of 4.

We can calculate the height of the tree using recursive method very easily. It is based on the observation that height of a binary tree is 
1 + Max( height(left-sub-tree), height(right-sub-tree) )
Here is the C++ code which implements this simple algorithm.

How to insert into a binary search tree

A binary search tree is a hierarchical data structure which stores data in a non-linear fashion. It supports the insertion, search and deletion operations in O( log n ) time. Take a look at the below picture.

This is an example of binary search tree. The node at the top containing 5 is the root and all the elements to the left of it(left sub-tree) are less than 5 and all the elements to the right of it (right sub-tree) are greater than 5. A binary search tree does not allow duplicate elements in it. 
In this post we see how an insertion method works. It works very similar to the binary search.

The insert method looks at the root. If the given data is lesser than root data, it has to be inserted into the left sub-tree. Otherwise it has to be added in the right sub-tree. Since the left/right sub-trees are also binary search trees, we call the procedure recursively.
Here is the complete C++ program which implements a binary search tree in Object Oriented approach. I have used in-order traversal to print all the elements of the binary search tree. These procedures are explained in future posts.

Finding the least common ancestor (LCA) in a binary search tree

Given a Binary Search Tree (BST), How do we find the Lowest Common Ancestor (LCA) of the given two nodes?

For example in the following BST, the LCA of 5 and 8 is 7 because it is the nearest ancestor common to both the nodes.

Let us assume that the LCA(5,7) is 7 itself ( i.e We can consider that a node is a ancestor of itself).
           4
          /
         2   7
            /
           5   9
              /
             8

We start at the root node and check if the data at root node lies between the given two nodes. If it is we have found the LCA. If the root data is lesser than the given two nodes, we ignore the left sub-tree and continue with the right-sub tree. If the root data is greater than given two nodes, we ignore the right sub-tree and repeat the same procedure with the left sub-tree.

This approach assumes that the given two nodes are present in the tree.

It runs in O( n log n) on average. and O(n) in worst case( skewed BST).

Following is the Java code which implements the above algorithm.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/27/13
* Time: 10:58 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
tree.insert(4);
tree.insert(8);
tree.insert(2);
tree.insert(3);
tree.insert(1);
tree.insert(5);
tree.insert(9);

System.out.println("The lease common ancestor of 9 and 1 is " + tree.findLCA(9,1).getData()) ;
System.out.println("The lease common ancestor of 4 and 8 is " + tree.findLCA(4,8).getData()) ;
}
//Define Binary Search Tree Node
static class BSTNode
{
public BSTNode(int d )
{
data = d;
left = null;
right = null;
}
public BSTNode(int d, BSTNode l, BSTNode r)
{
data = d;
left = l;
right = r;
}
public int getData()
{
return data;
}
public void setData(int d)
{
data = d;
}

public BSTNode getLeft()
{
return left;
}

public void setLeft(BSTNode l)
{
left = l;
}
public BSTNode getRight()
{
return right;
}

public void setRight(BSTNode r)
{
right = r;
}
private int data; //data
private BSTNode left; //left subtree
private BSTNode right; //right subtree
}
//Define Binary Search Tree
static class BinarySearchTree
{
public BinarySearchTree()
{
root = null;
}
public BSTNode getRoot()
{
return root;
}
//Finds the least common ancestor for the given two nodes
public BSTNode findLCA(int a, int b)
{
//Find the two nodes with given values
BSTNode nodeA = find(a);
BSTNode nodeB = find(b);

BSTNode r = root;

while ( r != null )
{
if( r.getData() < a && r.getData() < b )
r = r.getRight();
else if( r.getData() > a && r.getData() > b)
r = r.getLeft();
else
break;
}
return r;
}
//Finds the BST node with the given data
public BSTNode find(int d)
{
BSTNode r = root;

while ( r != null && r.getData() != d )
{
if( r.getData() == d )
break;
else if( r.getData() < d )
r = r.getRight();
else
r = r.getLeft();
}
return r;
}
//inserts the given data into a BST
public void insert(int d)
{
if( root == null )
{
root = new BSTNode(d);
}
else
{
BSTNode current = root;
BSTNode prev = null;
while( current != null )
{
prev = current;
if( current.getData() < d )
{
current = current.getRight();
}
else
{
current = current.getLeft();
}
}
if( d < prev.getData() )
{
prev.setLeft( new BSTNode(d));
}
else
{
prev.setRight(new BSTNode(d));
}
}
}
private BSTNode root;
}
}