How to find the lowest common ancestor in binary tree

There are many ways in which we can calculate the lowest common ancestor of two nodes. We will discuss two common methods.

Brute Force Tree Traversal

In this method we will iterate from the node a to the root of the tree, while saving the ancestors of the node in a vector. Next, we will iterate from the node b to the root of the tree and determine whether the ancestors of a appear in the ancestors of b. The first ancestor of b which is also an ancestor of a will be the lowest common ancestor. This method will require a total of two traversals of the binary tree.

Time-Complexity

This method will require a total of two traversals of the binary tree. So the Time-Complexity will be O(2h) ≈ O(h) where h is the height of the tree.

Space-Complexity

This method will store the ancestors of node a in a vector. So in the worst-case scenario, a is the leaf of the tree at the greatest depth. So a would have h ancestors. The Space-Complexity would hence be O(h).

Implementation

Below we have defined a binary tree in C++ and python that has the same structure as the illustration above.

#include <iostream>
#include <string>
#include <iomanip> 
#include <vector>
using namespace std;
struct Node{
  public : 
    char data;
    Node *left_Node;// The left subtree of the node  
    Node *right_Node; // The right subtree of the node
    Node *parent;
    // Constructor method;
    Node(char input_data){
      data = input_data; // Initializes the Node data to input data
    }
};
Node* return_node(char input_data){
  Node *newnode = new Node(input_data);
  return (newnode);
}
struct BinaryTree{
  public: 
    Node* root;
    // Utility functions
    BinaryTree(){
      root = NULL; 
    }
    BinaryTree(char input_data){
      root = return_node(input_data);
    }
};
Node* lowest_common_ancestor(Node *node1,Node *node2){
  vector<Node*> node1_ancestors;// Initialize a vector to store information in
  Node* curr = node1;
  
  while(curr!=NULL){
    curr = curr -> parent;
    if(curr!=NULL){
      node1_ancestors.push_back(curr);// Store the ancestors of node1
    }
  }
  Node* lowest_ancestor = NULL;
  curr = node2;
  while(curr!=NULL){
    curr = curr->parent;
    for(int i=0;i<node1_ancestors.size();i++){
      if(node1_ancestors[i]==curr){ // Find the first ancestor common to both node1 and node2
        lowest_ancestor = curr;
        return lowest_ancestor;// Return THE lowest common ancestor
      }
    }    
  }
  return lowest_ancestor;// Otherwise return null
}
int main() {
  // Initializing a binary tree
  struct BinaryTree newTree('d');
  // Adding left and right plus the parent for each node
  newTree.root->left_Node = return_node('c');
  newTree.root->left_Node->parent = newTree.root;  
  newTree.root->right_Node = return_node('e');
  newTree.root->right_Node->parent = newTree.root;
  newTree.root->left_Node->left_Node = return_node('a');
  newTree.root->left_Node->left_Node->parent =newTree.root->left_Node;
  newTree.root->left_Node->right_Node = return_node('b');
  newTree.root->left_Node->right_Node->parent =newTree.root->left_Node;
  newTree.root->right_Node->left_Node = return_node('f');
  newTree.root->right_Node->left_Node->parent =newTree.root->right_Node;
  newTree.root->right_Node->right_Node = return_node('g');
  newTree.root->right_Node->right_Node->parent =newTree.root->right_Node;  
  
  // Call the method of two of the nodes
  Node* result = lowest_common_ancestor(newTree.root->right_Node->right_Node,newTree.root->right_Node->left_Node);
  cout <<"Node 1: "<<newTree.root->right_Node->right_Node->data<<endl;
  cout<<"Node2 : "<<newTree.root->right_Node->left_Node->data<<endl;
  cout <<"lowest common ancestor : "<< result->data<<endl;
  
}

Recursive Tree Traversal

In this method we will use recursion to reduce the time required to find the lowest common ancestor. We will start from the root and traverse the tree towards the leaves. This method uses four if conditions.

If the current node is NULL then we will return NULL since we have reached the end of the tree.
If the current node matches nodes a or b, we will return the current node.
If the current node has node a in its left subtree and b in its right subtree or vice versa then the current node will be the lowest common ancestor.
If the current node has nodes a and b exclusively in its left subtree or right subtree, then we will return the left or right subtree accordingly.

Time-Complexity

This method will require one traversal of the binary tree. So the Time-Complexity will be O(m+n) ≈ O(n) where m is the number of edges and n is the total number of nodes.

Space-Complexity

Another advantage of this method is that it does not use any data structure to store the ancestors of the nodes a and b. Hence, the space-complexity will be O(n).

Implementation

The problem has been solved in C++ and python. This method uses the same four conditions as described above.

#include <iostream>
#include <string>
#include <iomanip> 
#include <vector>
using namespace std;
struct Node{
  public : 
    char data;
    Node *left_Node;// The left subtree of the node  
    Node *right_Node; // The right subtree of the node
    Node *parent;
    //Constructor method;
    Node(char input_data){
      data = input_data; //initializes the Node data to input data
    }
};
Node* return_node(char input_data){
  Node *newnode = new Node(input_data);
  return (newnode);
}
struct BinaryTree{
  public: 
    Node* root;
    //utility functions
    BinaryTree(){
      root = NULL; 
    }
    BinaryTree(char input_data){
      root = return_node(input_data);
    }
};
Node* lowest_common_ancestor(Node *curr,Node *node1,Node *node2){
 if(curr==NULL){// if the curr node is NULL return NULL because we have reached the leaf
   return NULL;
 }else if(curr==node1 || curr==node2){// if the current node is either node1 or node2, return the current node.
   return curr;
 }
 Node *left_subtree = lowest_common_ancestor(curr->left_Node,node1,node2);
 Node *right_subtree = lowest_common_ancestor(curr->right_Node,node1,node2);
if(left_subtree!=NULL && right_subtree!=NULL){// if the curr node has node1 and node2 in it's left subtree and right subtree. Return the current node
  return curr;
}else if(left_subtree!=NULL){//return the left subtree
  return left_subtree;
}else{
  return right_subtree;//otherwise return the right subtree.
}
  return NULL;//lowest common ancestor is not found
}
int main() {
  // initializing a binary tree
  struct BinaryTree newTree('d');
  // adding left and right plus the parent for each node
  newTree.root->left_Node = return_node('c');
  newTree.root->left_Node->parent = newTree.root;  
  newTree.root->right_Node = return_node('e');
  newTree.root->right_Node->parent = newTree.root;
  newTree.root->left_Node->left_Node = return_node('a');
  newTree.root->left_Node->left_Node->parent =newTree.root->left_Node;
  newTree.root->left_Node->right_Node = return_node('b');
  newTree.root->left_Node->right_Node->parent =newTree.root->left_Node;
  newTree.root->right_Node->left_Node = return_node('f');
  newTree.root->right_Node->left_Node->parent =newTree.root->right_Node;
  newTree.root->right_Node->right_Node = return_node('g');
  newTree.root->right_Node->right_Node->parent =newTree.root->right_Node;  
  
  // call the method of two of the nodes
  Node* result = lowest_common_ancestor(newTree.root,newTree.root->right_Node->right_Node,newTree.root->right_Node->left_Node);
  cout <<"lowest common ancestor for nodes "<<newTree.root->right_Node->right_Node->data<< " and "<<newTree.root->right_Node->left_Node->data<<" is : " << result->data<<endl;
  return 0;
}

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to find the lowest common ancestor in binary tree

What is the lowest common ancestor?

Brute Force Tree Traversal

Time-Complexity

Space-Complexity

Implementation

Recursive Tree Traversal

Time-Complexity

Space-Complexity

Implementation