Lowest common ancestor in binary search tree

Image result for binary search tree images

    In the above tree if you see node 1 the ancestors(nodes which are higher in hierarchy) are 3, 8. And for 4 the ancestors are 3,6 and 8. So the lowest(close to both nodes) common ancestor of 1 and 4 is 3.

    Now for a given nodes v1 and v2 we have to find the lowest common ancestor of both nodes.

    In binary search tree if a given value say v1 is lesser than the present node then it is definitely lies in the left subtree. Similarly if the given value is greater than the present node then it lies in the right subtree. Using this property we will solve the example problem as shown below.


Solving the problem:
We will follow the below steps to find the lca of 1 and 4.

1. We will be starting with the root node which is 8. Both 3 and 4 is less than 8, so we will go to left subtree of 8.
2. current node is 3. Here 1 is less than 3 but 4 is greater than 3. This is the key point of the problem. At node 3 one value is less other value is greater. Which means one will be present in left subtree and other value will present in right subtree. So hereafter there is no possibility for them to have common ancestors as both of them are travelling in different directions.

 Algorithm:
1. Visit the  node (root node initially). 
2. If both the given values are less than the node visit the left subtree and continue step 1
3. If both the given values are greater than the node visit the right subtree and continue step 1.
4. else return node.

Code:
static Node lca(Node root,int v1,int v2)
    {
        while(true){
            if( v1 > root.data && v2 > root.data )
                root = root.right;
            else if( v1 < root.data && v2 < root.data )
                root = root.left;
            else
                break;
        }
  
        return root;
    }


     

Comments

Post a Comment

Popular posts from this blog

Tree traversals - Inorder Traversal

Image
        A binary tree can be traversed in two ways. i) Depth First Traversal: Inorder, preorder, postorder ii) Breadth First Traversal: Level Order Traversal Inorder traversal:        In inorder traversal root is visited in between left and right subtree traversals. Steps: 1.  Traverse the left subtree 2.  Visit the root 3. Traverse the right subtree Note: If binary search tree is traversed in inorder, the numbers will be sorted in ascending order. Code: void inOrder(Node root) { if(root==null) return; inOrder(root.left); System.out.print(root.data+" "); inOrder(root.right); } Illustration: Inorder traversal of given tree is 3, 5, 4, 7, 8  Consider the left subtree of 7 (since 7 is the root ,we always start our traversal from root) Here we start form 5, the left subtree of 5 is 3. For 3 the left subtree is empty , So we visit the root. The right subtree of tree is also empty. At ...
Read more

Binary Search tree (Insertion)

Image
   A tree in which every node can have a maximum of two children is called a binary tree.       A binary search tree is a binary tree in which every node has lower values in the left sub tree and higher values in the right sub tree. Node of binary tree: class Node{      int data;      Node left, right;      Node(int data){         this.data = data;         right = left = null;      } } BST - Insertion:  static Node Insert(Node root,int data) {      if( root == null ){            root = new Node(data);            return root;      }      if( data < root.data)             root.left = Insert(root.left,data);      else             root.right = Insert(root.rig...
Read more

Stack implementation using array

Image
    Introduction:    Stack is a linear data structure which follows LIFO( Last In First Out ) order.   To represent stack consider books are placed in table for the teacher to correct. The note which is submitted last will be corrected first. The person who submits last is quite unlucky isn't it :P Operations: push: Inserts element at the top of the stack pop: Removes element from the top of the stack Stack implementation using array: Code: import java.util.*; import java.lang.*; import java.io.*; class Stack {     int SIZE = 10;     int arr[] = new int[SIZE];     int top = -1;          public int pop(){         if (top == -1){             System.out.println("stack is empty");             return 0;         }         int topelement ...
Read more