Lowest common ancestor in binary tree

Lowest common ancestor 

Given a binary tree, find lowest common ancestor of two given nodes. For example, in given binary tree, lowest common ancestor of node 9  and node 5 will be 2.
lowest common ancestor
We do not have luxury of BST property here, think of something else here.
What is the condition for a node to be Lowest common ancestor (LCA) of two nodes. Condition is that paths for both given nodes should diverge from the candidate node.Till the time we have path common for given nodes, we have common ancestors but they are not lowest. How can we find where paths are diverging?

Algorithm to find least common ancestor in binary tree

1. Find any one given node in binary tree.
2. Once one node is found, move up to parent and check if other resides on the other side of the parent.
3. If second node resides on other side of parent, then parent is LCA.
4. If it does not, continue to check parent of parent, till we reach root.
5. If we don't find any such node while moving up, LCA is the node which is found in step 1.

Lowest common ancestor : Implementation

For every node in tree, check for if any of the given nodes in left side of the node. As soon as we encounter a node which is equals to one of the nodes given, return that node. After that, check for other node in right sub tree of the parent of returned node. If we find other node on the right side of the parent node, then parent node is LCA.

If we found a node on left side and do not find other on the right side, then other node is below the returned node from left side, hence that node is LCA. If we don’t find any node in the left tree, then both nodes are on the right side of the node, move to right side of the node. Follow the procedure again.

Let’s take an example to see this algorithm work. we have tree as
lowest common ancestor

Find LCA of 2 and 5.For root 6, we would first move to left side and search for 2 and 5 in sub tree root at 3. Again we would search 2 and 5 in left sub tree in tree rooted at 3. In this step we would look for nodes in left sub tree of tree rooted at 2.

This time we would find 2 which is one of the two nodes. We would return node 2, let’s call it left. Once we get this node we would look on the right side of sub tree of the tree rooted at 3. Once again, we would hit one of nodes we are looking for i.e. We would return 5.let’s call it right. Now at node 3 we have both left and right as non-null, hence 3 is the lowest common ancestor.

Tip: We don’t need to look into the left and right tree of the node which is equal to one of nodes we are searching for, as in any case that would be the LCA if we don’t fins other node in right sub tree of parent . (Think loud!).We only need to look into the right part of the parent of the node, if the other node is on the right side of the parent, then this node cannot be LCA, but the parent is the LCA.

If we don’t find other node once we find one, we assume that the found node is the LCA, as other node can be below that node.

Consider another example, find LCA of 2 and 3.

1. We look on the left sub tree of tree rooted at 6.
2. We go to 3. 3 is the node we are looking for. return from here.
3. Check for the other node in right sub tree of parent node i.e 6.
4.  We would not find any of the nodes 2 or 3 on the right side of 6.
5. Hence we return node 3 as LCA.

So there is a problem here, what if there is only one node present in tree. we would report that node as LCA.

Node *lowestCommonAncestor(Node *node, int val1, int val2){
        if(!node)
                return NULL;
        if(node->value == val1 || node->value == val2)
                return node ;
 
        Node *l = lowestCommonAncestor(node->left, val1, val2);
        Node *r = lowestCommonAncestor(node->right, val1, val2);

       /*if we have found one node on right side of node 
         and other on left side
        then the given node is LCA */
        if(l && r)
                return node;

        /* if we have found one node on the left side,
         we don't look below that node, and we return 
         to parent node to look for right sub tree for 
         the other node */
        if(l)
            return l;

        /* if we have found one node on the right side, 
         we don't look below that node, and we return 
         to parent node to check if other node was found 
         in the left tree then return LCA */
        if(r)
            return r;
}

We would be scanning all nodes at once for comparison with the given nodes, hence worst complexity of finding lowest common ancestor in binary tree will be O(N).

Please share if there is something missing or wrong. If you are interested in contributing to website, please contact us.

Lowest common ancestor in binary search tree

Lowest common ancestor in binary search tree

We saw how find Kth smallest element in binary search tree can easily be solve by using BST property which states that all nodes on left subtree of a node are smaller and all nodes on right subtree are greater than node itself. Another problem which uses this property of Binary Search Tree (BST) is finding Lowest Common Ancestor commonly know as LCA.

Problem statement is : given two nodes of BST, find lowest node which is parent of both given nodes, that is least common ancestor (LCA). For example in following tree, LCA of 25 and 37 is 30

lowest common ancestor

Can we use property “all nodes on left subtree smaller and all nodes on right subtree are greater than node” to solve this problem?  Lowest common ancestor of two nodes will be the node when path of two nodes diverge, i.e. one node is greater than current node and other is greater.  For each candidate LCA, there are three cases to be considered:

Case 1 : Two nodes are less than current node.
In this case, there must be a node lower than current node on left subtree where these two nodes diverge. Hence, look for LCA in left subtree of current node.

Case 2 : Two nodes are greater than current node
In this case, there must be a node lower than current node on right subtree where these two nodes diverge. Hence, look for least common ancestor on right subtree of current node.

Case 3: One of the two nodes is parent of other.
In this case, LCA is parent node.

Case 4 : One node is on left and other on right side of current node. 
Then current node is least common ancestor of two nodes.

Implementation of lowest common ancestor algorithm

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
 
typedef struct node Node;
 
int leastCommonAncestor(Node *root, int val1, int val2){
 
 	if(!root)
       return -1;
 
 	if(root->value == val1 || root->value == val2)
    	return root->value;
 
 	/* Case 3 : If one value is less and other greater 
             than current node Found the LCA return */
 	if((root->value > val1 && root->value <= val2) ||
  		(root->value <= val1 && root->value >val2)){
           return root->value;
 	}
 	/*Case 1 : If Both values are less than current node, 
           look in left subtree */
 	else if(root->value < val1 && root->value <val2){
            return leastCommonAncestor(root->right, val1, val2);
 	}
  	/*Case 2 : If Both values are greater than current node, 
                   look in right subtree */
 	else if(root->value > val1 && root->value > val2){
            return leastCommonAncestor(root->left, val1, val2);
 	}
}
 
Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
 
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
 
  return newNode;
 
}
 
Node * addNode(Node *node, int value){
  if(!node) return createNode(value);

  if (node->value > value)
        node->left = addNode(node->left, value);
  else
        node->right = addNode(node->right, value);
 
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
 
  printf("\n least common ancestor: %d ",
              leastCommonAncestor(root, 15, 25));
 
  return 0;
}

LCA candidates reduce by half with every comparison. In worst case, number of comparisons will be equal to depth of tree. Depth of a tree, given tree is not completely skewed, is roughly log N, hence complexity of this algorithm is logN. If the tree is completely skewed and there is parent child relationship between given nodes, then we need to compare N nodes and our complexity becomes O(N) in worst case.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview problem to share, please contact us.

Find Kth smallest element in binary search tree

Finding Kth smallest element in an array is well know problem. Today’s problem is to find Kth smallest element in a binary search tree.

By Kth smallest node/number, we means that there are K-1 nodes in tree which are less value than this node. For example, first smallest node is smallest node in tree, second smallest node is one greater than the smallest and so on.

In below tree, 5th smallest node is : 37

Kth smallest element in binary search tree

Finding Kth smallest node is uses property of Binary Search Tree (BST) that all nodes on left side of a node are less than node and all nodes at right are greater than it.
If number of nodes on left side of current node, we can then decide whether Kth smallest node is present in left subtree or in right subtree of the current node. Based on this information, we can discard one half binary search tree and recursively look for node in left or right subtree only.

Algorithm to find Kth smallest element in BST

1. Start from root, be it currentNode 
2. Check number of nodes on left subtree be it X
   2.1 If X is less than K, then search Kth smallest in right subtree
   2.2 If X is greater than K, search for Kth smallest in left subtree
   2.3 If X == K-1 then return currentNode.

Kth smallest element in binary search tree implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
 
typedef struct node Node;
 
/* This function calculates the size of tree rooted at Node */
int sizeOfLeftTree(Node *node){
  if(!node)
    return 0;
 
  return 1 + sizeOfLeftTree(node->left)
           + sizeOfLeftTree(node->right);
}
 
int findKthNode(Node *root, int K){
 
    if(!root)
      return 0;
 
    int no_left = sizeOfLeftTree(root->left); 
    /* If there are K-1 nodes in left sub tree */     
 
    if(no_left  == K-1){
      return root->value;
    }
   /* If there are more than K-1 nodes in left sub tree */
    else if(no_left > K-1){
      return findKthNode(root->left, K);
    }
    /* If there are less than K nodes in left sub tree */
    else{
      return findKthNode(root->right, K-no_left-1);
    }
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
 
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
 
  return newNode;
 
}
 
Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
 
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
 
  printf("\n Kth smallest node : %d ",
            findKthNode(root, 4));
 
  return 0;
}

Another method that can be easily implemented and suggested by skeptic in comments is to do inorder traversal of binary search tree and keep count when we are printing the node. Once count reaches K, we have found our desired node.

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
 
typedef struct node Node;
 
 
int findKthNode(Node * root, int *n, int K){
    if(!root) return -1;
 
    findKthNode(root->left, n, K);
    (*n)++;
    if(K == *n){
        return root->value;
    }
    findKthNode(root->right, n, K);
}
 
Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
 
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
 
  return newNode;
 
}
 
Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  int n = 0;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
 
  printf("\n Kth smallest node : %d ",
              findKthNode(root, &n, 4));
 
  return 0;
}

There is another method which is more simple and efficient. It requires inorder traversal of tree and keep track of the number of nodes visited. Once K nodes are traversal break the traversal. Same method can be used to find Kth largest element, where we do inorder traversal in reverse way.

For the first approach, at any point of time we would be discarding half of the nodes, so ideally it should be O(logN). However this is not the case. We are traversing the entire left side of the tree for every node to get the number of node s in left sub tree. Considering tree as balanced tree too, we would be traversing N/2 nodes for logN times, hence complexity of this solution is N log N and not logN. Hence, complexity of finding Kth smallest element in binary search tree with first approach will be O(NLogN). In second approach, we will traversing at most K nodes hence the complexity will be O(K).

Please share if there is something is missing or wrong. If you are willing to contribute to website or have an interview experience to share, please contact us.