Coding Recipies: Tree Operations

Discuss and give implementation of basic Tree operations.

Fig : A Binary Search Tree with root 15

Solution:

From the below table of complexities we can clearly see that why one sholud prefer Tree data structure compared to Linked List , Array (Sorted or Unsorted) .

I Introduction to BST :

A BST is a data structure which is dynamic in nature as Linked Lists. It is advantageous over Linked List or arrays because the basic operations of

Add
Delete
Search
Get

are cheaper in BST compared to Arrays or Linked List.

The performance of operation's mentioned above depends on the height of the Tree. To take care of that , concept of balancing comes into picture which can be achieved by AVL Trees and Red-Black Trees.

A Binary Search Tree is Binary Tree which satisfies the following properties.

It is a Binary Tree
Each Node has a has a 'left' , a 'right' pointer and a data element
Contains a 'root'node which is reference to the whole tree.
left sub tree contains values lesser than the node's value (true for nodes except leaf nodes)
right sub tree contains values greate than the node's value (true for nodes except leaf nodes)
Contains Leaf nodes whose left and right pointers point to NULL.

A Binary Search Tree (BST) or "ordered binary tree" , is a kind of binary tree in such way that the nodes are arranged in order , i.e. for each node all elements in its left sub tree are lesser than the node and all the elements in its right sub-tree are greater or equal to node.

The Node structure in a Tree is shown below :

/**
 * Node Class of Tree
 * @author Prateek
 *
 */
public class Node implements Comparable<Node> {
 public Node left;
 public int data;
 public Node right;

 public Node(int val)
 {
  this.data=val;
 }

 @Override
 public int compareTo(Node that) {
  return this.data - that.data ;
 }
 
 @Override
 public String toString(){
  return this.data + "";
 }
 
}

II Binary Search Tree Operations:

Please refer to full Source Code

1. Insertion:
This operation can be in a BST means insertion into the tree such that BST property is maintained.
Recursive and non-recursive implementation of this operation is given below.

1a. Recursive Procedure:

// Using recursion
 public void recinsert(Node root, int val) {
              if (val < root.data)    {
         if (root.left != null)
          recinsert(root.left, val);
         else
             root.left = new Node(val);
     } 
     else if (val > root.data)     {
         if (root.right != null)
          recinsert(root.right, val);
         else
             root.right = new Node(val);
     }
 }

1b. Non- Recursive Procedure:

// using non-recursive
 public void insert(int val, Node root) {
  Node newNode = new Node(val);

  // if tree is null
  if (root == null)
   root = newNode;

  else {
   Node parent = null;
   Node child = root;

   while (true) {
    parent = child;

    // Move left
    if (newNode.data &lt; child.data) { 
     child = child.left;
     if (child == null) {
      parent.left = newNode;
      return;
     }

    // Move Right
    } else {
     child = child.right;
     if (child == null) {
      parent.right = newNode;
      return;

     }
    }
   }
  }
 }

2. Contains

This operations finds the given number in the BST and return true and in case number is not found false is returned.

Recursive as well as Non- recursive Implementation is given below:

2a. Non Recursive :
Node Class has implemented Comparable interface.

public boolean contains(Comparable item , Node root){
  Node temp=root;
  
  while(temp!=null) {
   int result = item.compareTo(temp.data) ;
   
   if(result == 0)
    return true;
   
   else if (result > 0) 
    temp=temp.right;
   
   else
    temp=temp.left ;
  }
  
  return false;
 }

2b. Recursive Approach:

/**
  * IsContains
  * @param item : Number to be searched 
  * @param root: Root of the tree
  * @return true if contained in the tree, else false
  */
 public boolean reccontains(Comparable item , Node root){
  
  if(root==null)
   return false;
  
  int result = item.compareTo(root.data) ;
  
  if(result < 0)
  return reccontains(item , root.left) ;
  
  else if(result > 0)
  return reccontains(item , root.right) ;
  
  else return true;
 }

3 Get Operation :
This returns the value of the Node object passed if it is contained in the tree.

3a. Recursive approach

//---------------Get Operation--------
 /**
  * Recursive Get Operations
  * @param item  : Node object for which value is being searched
  * @param root  : root of the tree
  * @return : -1 if not found or tree is null else return the value of the
  *         Node that was being searched
  */
 private Comparable recGet(Comparable item, Node root) {
  if (root == null)
   return -1;

  if (item.compareTo(root.data) < 0)
   return recGet(item, root.left); // retrieve from left subtree
  else if (item.compareTo(root.data) > 0)
   return recGet(item, root.right); // retrieve from right subtree
  else
   return root.data;
 }

3b. Non Recursive Approach :
Try yourself.

4. Height of the Tree
Height of the tree is considered to be that height from the root to leaf node such that the path is longest in the tree.

To calculate the same there are recursive as well as non recursive approach.

4a. Recursive approach:

/**
  * Height (recursively)
  * @param root
  * @return
  */
 public int height(Node root) {
  if (root == null) 
   return 0;
   else {
   int lHeight = height(root.left);
   int rHeight = height(root.right);

   if (lHeight > rHeight)
    return lHeight + 1;
   else
    return rHeight + 1;

   // return max(height(node.left),height(node.right)) + 1
  }
 }

4b. Non Recursive approach:

The concept is to traverse the tree level by level using a queue , maintain a count , and at each level increment the count.
Please search level order traversal using queue in this blog.

5. Traversals
Traversal means walk through the tree, traversal can be made by any of the three ways mentioned below:
a) Inorder Traversal :
For any node N and its childs L and R , it is expressed as
Inorder is : L N R
or for any mathematical operation with operands 'A' and 'B' , and operator '+'.
Inorder is : A + B
e.g. inorder traversal of given tree is : 3 , 5 , 6 , 7 , 12 , 13 , 15 , 16 , 18 , 23

b) PreorderTraversal :
For any node N and its childs L and R , it is expressed as
Pre-order is : N L R
or for any mathematical operation with operands 'A' and 'B' , and operator '+'.
Pre-order is : + A B
e.g. preorder traversal of given tree is : 15 , 5 , 3 , 12 , 10 , 6 , 7 , 13 , 16, 20 , 18 , 23

c) Post orderTraversal :
For any node N and its childs L and R , it is expressed as
Post-order is : L R N
or for any mathematical operation with operands 'A' and 'B' , and operator '+'.
Post-order is : A B +

e.g. postorder traversal of given tree is : 3 , 7 , 6 , 10 , 13 , 12 , 5 , 18 , 23 , 20 , 16 , 15

Recursive approach for the all of the above is given below:

public void inorder(Node root) {
  if (root != null) {
   inorder(root.left);
   System.out.println(root.data);
   inorder(root.right);
  }
 }

 public void preorder(Node root) {
  if (root != null) {
   System.out.println(root.data);
   preorder(root.left);
   preorder(root.right);
  }
 }
 
 public void postorder(Node root) {
  if (root != null) {
   postorder(root.left);
   postorder(root.right);

   System.out.println(root.data);

}
 }

Morris Traversal is used for traversing iteratively(non-recursively) , which we can discuss in some other post.

6. Predecessor of a Node
It is the largest item in the tree that is strictly smaller than the given element. Null if there is no such node.

If you observe carefully in the above diagram that Predecessor of node can be calculated by moving down to the left child and then return the rightmost child of that sub -tree.

Implementation (non- recursive)

/**
  * @param node of tree
  * @return Predessor of a given Node
  */
 public Comparable getPredecessor(Node root,int val) {
  if(root == null)
   return null;

  Node pred = null;
  Node curr = root;
  while (curr!=null && curr.data != val) {
   // Move left
   if (val < curr.data) 
    curr = curr.left;

   // Move Right
   else {
    pred = curr;
    curr = curr.right;
   }
  }

  if(curr.left==null){
   return pred;
  }
  else
  {
   pred = curr.left;
   while (pred.right != null)
    pred = pred.right;
   return pred;
  }

 }

7. Successor of a Node
It is the smallest item in the tree that is strictly greater than the given element. Null if there is no such node.

If you observe carefully in the above diagram that Successor of node can be calculated by moving down to the right child and then return the left child of that sub -tree.

e.g. successor of node 5 in the tree is 6.

8. Min Value
It is the minimum value in a non-empty BST , it can be calculated by returning the leftmost child of the root. Similarly the max value will be the rightmost child of the root.
e.g. min value is the given tree is 3

public Comparable getSuccessor (Node root , int val) {
  if(root == null)
   return null;

  Node succ = null;
  Node curr = root;
  while (curr!=null && curr.data != val) {
   // Move Right
   if (val > curr.data) 
    curr = curr.right;

   // Move left
   else {
    succ = curr;
    curr = curr.left;
   }
  }

  if(curr.left==null){
   return succ;
  }
  else
  {
   succ = root.right;
   while (succ.left != null)
    succ = succ.left;
   return succ;
  }
 }

9. Contains path equal to a given sum
Given a tree and a sum , returns true if there is a path from the root down to a leaf , such that adding up all the node values along the path equals the given sum.

The approach is to subtract the node value from the sum and check if sum reduces to 0 at the end of the path, i.e. when null is reached.

/**
     * To find if the tree contains any path equal to given Sum
     * @param root
     * @param sum
     * @return
     */
 public boolean hasPathSum(Node root, int sum) { 
  // return true if repeated differnce has reached to 0 
  if (root == null) { 
   return(sum == 0); 
  } 
  else { 
   int subSum = sum - root.data; 
   return(hasPathSum(root.left, subSum) || hasPathSum(root.right, subSum)); 
  } 
 }

10. Is given Binary Tree a BST
For the problem we will have to check every node if it satisfies the BST property. If any node in the tree violates BST property , the given Binary tree will not be a BST.

BST Property : Left child is smaller than the parent and the right child is equal of greater the the parent.
For calculating the efficient solution to this problem we will be passing minimum and maximum value to the procedure , it order avoid unnecessary recursion (reducing overhead of calculating maximum and minimum value in the tree for this operation) .

public boolean isBST() {
    return( isBST(startnode, Integer.MIN_VALUE, Integer.MAX_VALUE) );
    }
 
    public boolean isBST(Node node, int min, int max) {
    if (node==null)
    return true;
 
    if (node.data < min || node.data > max)
    return false;
 
    boolean leftStatus = isBST(node.left, min, node.data - 1);
 
    if (!leftStatus)
    return false;
 
    boolean rightOk = isBST(node.right, node.data+1, max);
 
    return rightOk;
 
    // isBST(node.left, min, node.data - 1) && isBST(node.right, node.data+1, max)
    }

11. Size of BST
This operation returns the number of nodes in the BST.
This can be calculated by summing up LeftHeight , RightHeight and adding 1 (the node itself) . There are other approaches as well.

// -------------------Size of Tree--------------------------
 public int size(Node root) {
  if (root == null)
   return 0;
  else
   return (size(root.left) + 1 + size(root.right));
 }

12. Mirror
Mirror a given BST and return the mirrored tree

Please refer to this post

13. Kth Largest Element in BST

// -------------kth largest element---------------------------

 public int KthLargest( int k){
  countlargest=0;
  KthLargest(root,k);
  return countlargest;
 }
 
 static int countlargest = 0;
 public void KthLargest(Node root, int k) {

  if (root == null)
   return;

  KthLargest(root.right, k);

  if (++countlargest == k) {
   System.out.println(k + " th largest element is : " + root.data);
   return;
  }

  KthLargest(root.left, k);
 }

14. Diameter of Tree :
              For explanation of this operation follow the provided link

Source Code

15. Least common Ancestor (LCA)

         Definition:     Let T be a rooted tree with n node. The lowest common ancestor between two nodes v and w is defined as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

e.g. for 3 and 13 LCA is 5

16. Level order Traversal of tree:

Level order traversal of the tree means walking through the tree level by level , starting from the root.
e.g. Level order traversal of given tree is :
                       15 , 5 , 16 , 3, 12 , 20 , 10 , 13 , 18 , 23 , 6 , 7

Please refer to link for source code

17. Now we compare the complexity of operations in BST compared to array and Linked List

Operation	BST	Array	Linked List
Find	O(log n)	O(log n)	O(n)
Insert	O(log n)	O(log n)	O(n)
Delete	O(log n)	O(log n) (but rezising)	O(n)

There are many more operations supported in BST , which i can update later in this post as per your suggestions and comments.

Below is the categorization of the available tree.

Please point out any errata in the post.

Happy Coding :)

In order to develop conceptual figures in mind follow the below link:
References: http://www.cs.princeton.edu/~rs/AlgsDS07/08BinarySearchTrees.pdf

Coding Recipies

16 Oct 2013

Tree Operations

Please refer to full Source Code

2 comments: