Binary Search Tree in Scala

In this post we are going to make a structure which is similar to Binary Search Tree (BST).

Each node contains an integer element and two child nodes. All the nodes having value less than the current node will be on the left and all nodes having value greater will be on right. If a node doesn't have any child then it will have empty node at that place.

From the description, we can deduce that there are two types on integer nodes - Empty and Non Empty. The operations can be to add a new node or to check if a node exists in the current tree. Hence lets define an abstract class IntNode with these two abstract functions.

IntNode.scala

abstract class IntNode {
  def incl(x: Int): IntNode
  def contains(x: Int): Boolean
}

This abstract class will have its first concrete implementation as Empty node. This is empty node, hence its contains function will always return false. The incl function will take an integer value and create a non-empty node. The code is as follows.

Empty.scala

class Empty extends IntNode {
  def incl(x: Int): IntNode = new NonEmpty(x, new Empty, new Empty)
  def contains(x: Int): Boolean = false
  override def toString = " . "
}

Another concrete implementation of IntNode is NonEmpty node which is as follows.

NonEmpty.scala

class NonEmpty(elem: Int, left: IntNode, right: IntNode) extends IntNode {

  def incl(x: Int): IntNode =
    if (x < elem)
      new NonEmpty(elem, left incl x, right)
    else if (x > elem)
      new NonEmpty(elem, left, right incl x)
    else
      this

  def contains(x: Int): Boolean =
    if (x < elem)
      left contains x
    else if (x > elem)
      right contains x
    else
      true

  override def toString = " { " + left + elem + right + " } "
}

The toString function is overridden to print Empty node as dot(.) and non-empty node in the order of left, element and then right node(s).

Let's first take the contains function. It compares the element x passed to it with current node element and takes a decision based on the BST property. If an element doesn't exists in the tree then it recursively reaches the Empty node of which the contains function returns false.

The incl function also uses the property of BST to add a new node. If the element already present in the list, then it avoids duplication by returning this reference. Otherwise it accordingly reconstruct the tree.

The sample Main class and its output are as follows.

Main.scala

object Main extends App {

  val t1 = new Empty
  println("t1 = " + t1)

  val t2 = t1 incl 4
  println("t2 = " + t2)

  val t3 = t2 incl 1
  println("t3 = " + t3)

  val t4 = t3 incl 5
  println("t4 = " + t4)

  val t5 = t4 incl 2 incl 7 incl 0
  println("t5 = " + t5)

  println("t1 contains 4 = " + (t1 contains 4))
  println("t2 contains 4 = " + (t2 contains 4))
  println("t5 contains 4 = " + (t5 contains 4))
  println("t5 contains 0 = " + (t5 contains 0))
  println("t5 contains 9 = " + (t5 contains 9))

  val t6 = t5 incl 1
  println("t6 = " + t6)

}

Output

t1 =  . 
t2 =  {  . 4 .  } 
t3 =  {  {  . 1 .  } 4 .  } 
t4 =  {  {  . 1 .  } 4 {  . 5 .  }  } 
t5 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  } 
t1 contains 4 = false
t2 contains 4 = true
t5 contains 4 = true
t5 contains 0 = true
t5 contains 9 = false
t6 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  } 

Building a Binary Tree using Inorder and Postorder Traversals in Java

class TNode
{
 int data;
 TNode left;
 TNode right;

 TNode(int d)
 {
  data = d;
  left= null;
  right=null;
 }
}

class TreeBuilder
{
 static int postIndex;
 static int[] in, post;
 TNode Start;

 static void setValue(int[] i, int[] p)
 {
  in = i;
  post = p;
  postIndex=in.length-1; //Change 1
 }

 static int findInIndex(int inStart, int inEnd, int value)
 {
  for(int i=inStart; i<=inEnd; i++)
   if(in[i]==value)
   return i;

  return -1;
 }

 //Main method with the logic for building tree using Pre and Inorder traversals
 static TNode buildTree(int inStart, int inEnd)
 {
  if(inStart>inEnd)
   return null;

  TNode node = new TNode(post[postIndex--]); //Change 2

  if(inStart==inEnd)
   return node;

  int inIndex = findInIndex(inStart, inEnd, node.data);
  
  //Change 3

  node.right=buildTree(inIndex+1, inEnd);
  node.left=buildTree(inStart, inIndex-1);

  return node;
 }
}

class TreeBuilderDemo 
{
 public static void main(String[] args) 
 {
  int[] in = {8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7};
  int[] post = {8, 10, 11, 9, 4, 5, 2, 6, 7, 3, 1};

  TreeBuilder.setValue(in, post);

  TNode start = TreeBuilder.buildTree(0,in.length-1);

  System.out.print("\nPreorder\t: ");
  printPreorder(start);

  System.out.print("\n\nInorder\t\t: ");
  printInorder(start);

  System.out.print("\n\nPostorder\t: ");
  printPostorder(start);

  System.out.println("");
 }

 static void printInorder(TNode node)
 {
  if (node == null)
   return; 

  printInorder(node.left);   
  System.out.print(node.data + "\t "); 
  printInorder(node.right);   
 }

 static void printPreorder(TNode node)
 {
  if (node == null)
   return; 

  System.out.print(node.data + "\t ");
  printPreorder(node.left);   
  printPreorder(node.right);   
 }

 static void printPostorder(TNode node)
 {
  if (node == null)
   return; 

  printPostorder(node.left);   
  printPostorder(node.right);   
  System.out.print(node.data + "\t ");
 }
}

Click here to learn Building a Binary Tree using Inorder and Preorder Traversals in Java.

Binary Search Tree in C Data Structure

In computer science, a binary search tree (BST) is a node based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

From the above properties it naturally follows that: Each node (item in the tree) has a distinct key.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.

A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13 

#include<stdio.h>
#include<conio.h>
#define null 0

struct t
{
 int data;
 struct t *left;
 struct t *right;
};

typedef struct t tree;
tree *ptr, *root, *q;

void inorder(tree *ptr); //left - root - right
void preorder(tree *ptr); //root - left - right
void postorder(tree *ptr); //left - right - root

void main()
{
 int val;
 char c='n';
 root = (tree *)malloc(sizeof(tree));

 clrscr();

 printf("Enter data: ");
 scanf("%d",&root->data);
 root->left=null;
 root->right=null;
 ptr=root; //set the current pointer to root

 fflush(stdin);
 printf("\nDo you want to add more nodes? (y/n)");
 c=getche();

 while(c!='n')
 {
  printf("\nEnter data: ");
  scanf("%d",&val);
  ptr=root;   //Every time start from root and traverse
  while(1)
  {
   if(val<ptr->data)
   {
    if(ptr->left==null)
    {
     q=(tree *) malloc(sizeof(tree));
     ptr->left=q;
     ptr=ptr->left;
     ptr->data=val;
     ptr->left=null;
     ptr->right=null;
     break;
    }
    else
     ptr=ptr->left;
   }
   else
   {
    if(ptr->right==null)
    {
     q=(tree *) malloc(sizeof(tree));
     ptr->right=q;
     ptr=ptr->right;
     ptr->data=val;
     ptr->left=null;
     ptr->right=null;
     break;
    }
    else
     ptr=ptr->right;
   }
  }

  printf("\nDo you want to add more nodes? (y/n)");
  c=getche();
 }

 printf("\n\n\n\n\nInorder:\n");
 inorder(root);

 printf("\n\nPreorder:\n");
 preorder(root);

 printf("\n\nPostorder:\n");
 postorder(root);

 getch();
}

void inorder(tree *ptr)
{
 //left - root - right
 if(ptr!=null)
 {
  inorder(ptr->left);
  printf("%d\t",ptr->data);
  inorder(ptr->right);
 }
}

void preorder(tree *ptr)
{
 //root - left - right
 if(ptr!=null)
 {
  printf("%d\t",ptr->data);
  inorder(ptr->left);
  inorder(ptr->right);
 }
}

void postorder(tree *ptr)
{
 //left - right - root
 if(ptr!=null)
 {
  inorder(ptr->left);
  inorder(ptr->right);
  printf("%d\t",ptr->data);
 }
}

Building a Binary Tree using Inorder and Preorder Traversals in Java

This is a well known problem where given any two traversals of a tree  such as inorder & preorder or inorder & postorder traversals we need to rebuild the tree.

The following algorithm demonstrates how to rebuild a binary tree from given inorder and preorder traversals:

Global Declarations
preIndex=0;
Structure tNode
{
int data;
tNode left=null;
tNode right=null;
}

Main
1. Set Inorder and Preorder traversals
2. startNode = buildTree(0, in.length-1)
3. printPreorder(startNode)
4. printInorder(startNode)
5. printPostorder(startNode)
6. Stop

buildTree(inStart, inEnd)
1. If (inStart>inEnd)
return NULL
   End If
2. Create a new tree node tNode with tNode.data = preorder[preIndex].
3. Increment a preIndex Variable to pick next element in next recursive call.
4. If(inStart == inEnd)
return tNode
   End If
5. Find the picked element’s index in Inorder. Let the index be inIndex.
6. tNode.left = buildTree (inStart, inIndex-1)
7. tNode.right = buildTree ( inIndex+1, inEnd)
8. return tNode.

Now consider the following example:

Preorder Traversal:    1    2    4    8    9    10    11    5    3    6    7

Inorder Traversal:       8    4    10    9    11    2    5    1    6    3    7

Iteration 1:

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘1’ is root for given sequences. By searching ‘1’ in Inorder sequence, we can find out all elements on left side of ‘1’ are in left subtree and elements on right are in right subtree. So we know below structure now.

Root – {1}

Left Subtree – {8,4,10,9,11,2,5}

Right Subtree – {6,3,7}

We recursively follow above steps and get the following tree.

Iteration 2:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}

Root – {3} Left Subtree – {6} Right Subtree – {7}

Iteration 3:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}		Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}	Done	Done

Iteration 4:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}			Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}		Done	Done
Done	R – {9} Left ST – {10} Right ST-{11}	Done	Done

Finally a program in Java to demonstrate this tree building using traversal paths.

class TNode
{
 int data;
 TNode left;
 TNode right;

 TNode(int d)
 {
  data = d;
  left= null;
  right=null;
 }
}

class TreeBuilder
{
 static int preIndex;
 static int[] in, pre;
 TNode Start;

 static void setValue(int[] i, int[] p)
 {
  in = i;
  pre = p;
  preIndex=0;
 }

 static int findInIndex(int inStart, int inEnd, int value)
 {
  for(int i=inStart; i<=inEnd; i++)
   if(in[i]==value)
   return i;

  return -1;
 }


 //Main method with the logic for building tree using Pre and Inorder traversals
 static TNode buildTree(int inStart, int inEnd)
 {
  if(inStart>inEnd)
   return null;

  TNode node = new TNode(pre[preIndex++]);

  if(inStart==inEnd)
   return node;

  int inIndex = findInIndex(inStart, inEnd, node.data);

  node.left=buildTree(inStart, inIndex-1);
  node.right=buildTree(inIndex+1, inEnd);

  return node;
 }
}

class TreeBuilderDemo 
{
 public static void main(String[] args) 
 {
  int[] in = {8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7};
  int[] pre = {1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7};

  TreeBuilder.setValue(in, pre);

  TNode start = TreeBuilder.buildTree(0,in.length-1);


  //Now we will traverse through the newly created tree to verify that it is proper
  System.out.print("\nPreorder\t: ");
  printPreorder(start);

  System.out.print("\n\nInorder\t\t: ");
  printInorder(start);

  System.out.print("\n\nPostorder\t: ");
  printPostorder(start);

  System.out.println("");
 }

 static void printInorder(TNode node)
 {
  if (node == null)
   return; 

  printInorder(node.left);   
  System.out.print(node.data + "\t "); 
  printInorder(node.right);   
 }

 static void printPreorder(TNode node)
 {
  if (node == null)
   return; 

  System.out.print(node.data + "\t ");
  printPreorder(node.left);    
  printPreorder(node.right);   
 }

 static void printPostorder(TNode node)
 {
  if (node == null)
   return; 

  printPostorder(node.left);   
   printPostorder(node.right);   
  System.out.print(node.data + "\t ");
 }
}

Output of the program