How To Find The Lowest Common Ancestor In Binary Tree

ExploreEXPLORE THE CATALOGSupercharge your career with 700+ hands-on coursesView All CoursesPythonJavaJavaScriptCReactDockerVue JSRWeb DevDevOpsAWSC#LEARNING TOOLSExplore the industry's most complete learning platformCoursesLevel up your skillsSkill PathsAchieve learning goalsProjectsBuild real-world applicationsMock InterviewsNewAI-Powered interviewsPersonalized PathsGet the right resources for your goalsLEARN TO CODECheck out our beginner friendly courses.PricingFor BusinessResourcesNewsletterCurated insights on AI, Cloud & System DesignBlogFor developers, By developersFree CheatsheetsDownload handy guides for tech topicsAnswersTrusted answers to developer questionsGamesSharpen your skills with daily challengesSearchCoursesLog InJoin for freeHow to find the lowest common ancestor in binary tree

What is the lowest common ancestor?

For two nodes, a and b, the lowest common ancestor c is the lowest node in the binary tree that has a and b as its descendants.

Two nodes may have more than one common ancestor, however, they can have only one lowest common ancestor

Example of the lowest common ancestor

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.

C++Python#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; }Run

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.

C++Python#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;}Run

Relevant Answers

Explore Courses

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved