Join Our 4-Week Free Gen AI Course with select Programs.

Request a callback

or Chat with us on

Finding the Lowest Common Ancestor of a Binary Tree

Basics of SQL
Basics of SQL
icon
12 Hrs. duration
icon
12 Modules
icon
2600+ Learners
logo
Start Learning

A Binary tree, a nonlinear data structure, is a fundamental concept in computer science. In this article, we will delve into its practical application by using Java to find the lowest common ancestor in a Binary tree, a problem that often arises in real-world scenarios.

Introduction

In a Binary tree, the lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants of the same ancestor. We have to find the common ancestor of those descendants that shared the ancestor of n1 and n2 located farthest from the root. We will explore methods to find the LCA in a binary tree, discussing their time and space complexities.

Problem Statement

Given a binary tree and two nodes, the task is to find their lowest Common Ancestor. Let’s consider the following binary tree, for example.

 

Example

binary tree

In this tree:

 

  • The LCA of nodes 4 and 5 is 2
  • The LCA of nodes 4 and 6 is 1.
  • The LCA of nodes 7 and 8 is 5.

Constraints

Let’s discuss the constraints of this problem

 

  • 0 < n < 10 ^ 5, where n is the number of nodes.
  • 0 < node.val < 10 ^ 9

Approach 1: By Storing Root n1 and Root To n2 Paths

One of the methods to find the Lowest Common Ancestor of two nodes in a binary tree is by storing the paths from the root to each of the two nodes and then comparing these paths to find the last common node. Because In any tree data structure, a unique path exists between any two nodes. Let’s see the algorithm of the Lowest Common Ancestor.

Algorithm

To find the lowest common ancestor of a binary tree, we will perform the following steps in our source code.

 

  • We must store the path from the root to n1 in a list. Let it be path1.
  • We must also store the path from the root to n2 in a list. Let it be path2.
  • After getting both obtained paths, traverse the node path until the node path is common and return the node that occurs just before the mismatch.

 

Let’s see “how we can find the path from the root node to the target node”.

 

  • We have to define the list of integers, such as the name of the list path. Then, pass it to a boolean-type recursive function, findPath, which accepts three arguments: root,val, and path.
  • If the root is null, then return false.
  • Push root.val in the path list.
  • If our root.val is equal to val, then return true, as we’ve found that the desired node is any of the subtrees.
  • We must remove the element at the last position in our path list.
  • In the list, if nothing is worked out, then return false.

Dry Run

We will dry-run this approach using this given tree before implementing this algorithm in a programming language.

 

Tree

binary tree dry 

Find the Lowest Common Ancestor of (4,5)

 

  • Find the root node to the node with value 4. The first path will be

 

[1 -> 2 -> 4]

 

  • Find the path from the root node to the node with value 5. path2

 

[1->2->5]

 

  • Now, we will traverse both paths until we find the same path. Since we found a second mismatch, we will return the value just before the second index, which is 2.

Find the Lowest Common Ancestor of (7,4)

 

  • Find the path from the root node to the node with value 7. The first Path will be

 

[1->2->4->7]

 

  • Find the path from the root node to the node with value 5. The second path will be

 

[1-> 2->4]

 

  • Now, we must traverse both lists until the path is the same. Here, we will read the last index of path1, but if we do not find any mismatch, we will return the node at the last index of path1.

 

Find the Lowest Common Ancestor of (5,8)

 

  • Find the path from the root node to the node with value 5. The path will be

 

[1-> 2->4]

 

  • Find the path from the root node to the node with value 8. The path will be

 

[1->3-> 7->8]

 

  • Once again, we must traverse both path lists until the path has the same value. At the 1st index, we encounter a mismatch in paths, so we will return the node present at the 0th index 1.

Java Implementation

import java.util.*; class BinaryTree{ static List<Integer> path1 ; static List<Integer> path2 ; static boolean findPath(Node root, int value, List<Integer> path){ if(root == null){ return false ; } path.add(root.value) ; if(root.value == value){ return true ; } if(findPath(root.left,value,path)|| findPath(root.right, value, path)){ return true ; } path.remove(path.size() -1) ; return false ; } static int findLCA(Node root, int node1, int node2){ if(!findPath(root,node1,path1)|| !findPath(root, node2,path2)){ System.out.println("Pleae enter valid input"); return -1 ; } int index ; for( index = 0;index< path1.size() && index < path2.size();index++){ if(path1.get(index) != path2.get(index)){ break ; } } return path1.get(index -1) ; } static int LCA (Node root, int node1, int node2){ path1 = new ArrayList<>() ; path2 = new ArrayList<>() ; return findLCA(root, node1, node2) ; } public static void main(String args[]){ Node root  = new Node(1) ; root.left = new Node(2) ; root.left.left  =new  Node(4) ; root.left.left.right = new Node(7) ; root.left.right = new Node(5) ; root.right = new Node(3) ; root.right.right = new Node(6) ; root.right.right.left = new Node(8) ; root.right.right.right = new Node(10) ; System.out.println("LCA of  4 and 5 is "+LCA(root, 4, 5)) ; System.out.println("LCA of 7 and 4 is "+ LCA(root,7,4)); System.out.println("LCA of 5 and 8 is "+ LCA(root,5,8)) ; System.out.println("LCA of 5 and 10 is "+LCA(root,5,10)) ; } } class Node { int value ; Node left,right ; Node(int value){ this.value = value ; } }

Output

LCA of  4 and 5 is 2 LCA of 7 and 4 is 4 LCA of 5 and 8 is 1 LCA of 5 and 10 is 1

C++ Implementation

#include<bits/stdc++.h> using namespace std;  class Node{ public: int val; Node *left, *right;  Node(int Val){ val = Val; left = nullptr; right = nullptr; } }; vector<int> path1; vector<int> path2;  bool findPath (Node *root, int val, vector<int> &path){ if (root == nullptr) return false;  path.push_back(root->val);  if(root->val == val){ return true; }  if(findPath(root->left, val, path) || findPath(root->right, val, path)){ return true; }  path.pop_back();  return false; }  int findLCA(Node *root, int n1, int n2){  if (!findPath(root, n1, path1) || !findPath(root, n2, path2)){ cout << "Please enter valid input" << endl; return -1; }  int ind; for (ind = 0; ind < path1.size() && ind < path2.size(); ind++){ // If there is a mismatch break the loop. if(path1[ind] != path2[ind]) break; }  return path1[ind - 1]; } static int LCA(Node *root, int n1, int n2) { path1.clear(); path2.clear(); return findLCA(root, n1, n2); } int main() { Node *root = new Node(1); root->left = new Node(2); root->left->left = new Node(4); root->left->left->right = new Node(7); root->left->right = new Node(5); root->right = new Node(3); root->right->right = new Node(6); root->right->right->left = new Node(8); root->right->right->right = new Node(9);  cout << "LCA of 4 and 5 is " << LCA (root, 4, 5) << endl; cout << "LCA of 7 and 4 is " << LCA (root, 7, 4) << endl; cout << "LCA of 5 and 8 is " << LCA (root, 5, 8) << endl; cout << "LCA of 5 and 10 is " << LCA (root, 5, 10) << endl; }

Output

LCA of 4 and 5 is 2 LCA of 7 and 4 is 4 LCA of 5 and 8 is 1 LCA of 5 and 10 is Please enter valid input -1

Python Implementation

class Node:  def __init__(self, value): self.value = value self.left = None self.right = None  path1 = [] path2 = []  def findPath (root, value, path): if (root == None): return False  path.append(root.value)  if(root.value == value): return True  if(findPath(root.left, value, path) or findPath(root.right, value, path)): return True  path.pop() return False  def findLCA(root, n1, n2):  if (findPath(root, n1, path1) == False or findPath(root, n2, path2) == False): print("Please enter valid input") return -1  ind = 0 while( ind < len(path1) and ind < len(path2)): if(path1[ind] != path2[ind]): break ind+=1  return path1[ind - 1]  # Function to find the Lowest common ancestor def LCA(root, n1, n2): global path1, path2 path1 = [] path2 = []  return findLCA(root, n1, n2)  root = Node(1) root.left = Node(2) root.left.left = Node(4) root.left.left.right = Node(7) root.left.right = Node(5) root.right = Node(3) root.right.right = Node(6) root.right.right.left = Node(8) root.right.right.right = Node(9)  print("LCA of 4 and 5 is ", LCA (root, 4, 5)) print("LCA of 7 and 4 is ", LCA (root, 7, 4)) print("LCA of 5 and 8 is ", LCA (root, 5, 8)) print("LCA of 5 and 10 is ", LCA (root, 5, 10))

Output

LCA of 4 and 5 is  2 LCA of 7 and 4 is  4 LCA of 5 and 8 is  1 Please enter valid input LCA of 5 and 10 is  -1

Complexity Analysis

Time Complexity: In the worst case. We have to traverse the whole binary tree. It requires O(n) time to find the Lowest Common Ancestor.

Space Complexity:  The overall space of the binary tree is O(h).

Approach 2 – Using Single Traversal (Recursive Approach)

In the previous approach, we used traversing twice (once to find the path from the root node to the target node and from the root node to the 2nd target node. Now, we will optimise this approach so that it requires only one traversal to find the lowest ancestor of a binary tree with the lowest common ancestor.

Algorithm

Let’s look at the algorithm used to find the lowest common ancestor of a binary tree, as follows.

 

  • For example, let’s define two boolean values, b1 and b2, which will help us verify whether both keys provided as the input exist in a binary tree.
  • Then, a recursive function named find LowestCommontAncesstor is defined, and it accepts three arguments: node, n1, and n2.
  1. In this function, you must define the base condition that returns null whenever the node is null.
  2. Define a variable answer that initializes it to be null.
  3. You must check if the node’s value equals n1, make b1 true, and set the node to the answer.
  4. Otherwise, you have to check if node.value is equal to n2, make b2 true, and assign the node to answer.
  5. Recursive the left and right subtree and store their return values in the variables. We can define variables leftAnswer and righAnswer.
  6. If we find that the answer is no longer equal to null, then we will return it.
  7. Otherwise, If we find that both the leftAns and rightAns are not null, we will return the node.

 

  • Both values b1 and b2 are true or not. If they both are true, we will return the node value returned by the recursive function. Otherwise, we will return -1.

Java Implementation

class BinaryTree2{ static boolean b1,b2 ;  static Node findLCA(Node node, int node1,int node2){ if(node == null) return null ;  Node answer = null ;  if(node.value == node1){ b1 = true ; answer = node ; } else if (node.value == node2){ b2 = true ; answer = node ; }  Node leftAnswer = findLCA(node.left, node1,node2) ; Node rightAnswer = findLCA(node.right,node1,node2) ;  if(answer != null) return answer ;  if(leftAnswer != null && rightAnswer != null){ return node ; }  return leftAnswer !=null ? leftAnswer : rightAnswer ; }  static int LowestCommmonAncestor(Node root, int node1, int node2){ b1 = false ; b2 = false ;  Node lca = findLCA(root, node1, node2) ;  if(b1 && b2){ return lca.value ;  } System.out.println("Please Enter Valid Input") ; return -1 ;  } public static void main(String args[]){  Node root = new Node(101) ; root.left = new Node(102) ; root.left.left = new Node(104) ; root.left.left.right  = new Node(107) ; root.left.left.right = new Node(105)   ; root.right = new Node(103) ; root.right.right = new Node(106); root.right.right.left = new Node(108)  ; root.right.right.right = new Node(109) ;  System.out.println("Lowest Common Ancestor of 4 and 5 is "+LowestCommmonAncestor(root,104,105))   ; System.out.println("Lowest Common Ancestor of 7 and 4 is"+LowestCommmonAncestor(root,107,104))    ; System.out.println("Lowest Common Ancestor of 5 and 8 is "+LowestCommmonAncestor(root,105,108))   ; System.out.println("Lowest Common Ancestor of 5 and 10 is "+LowestCommmonAncestor(root,105,10)) ;  } }  class Node { int value ; Node left, right ;  Node(int value){ this.value = value ; } }

Output

Lowest Common Ancestor of 4 and 5 is 104 Please Enter Valid Input Lowest Common Ancestor of 7 and 4 is-1 Lowest Common Ancestor of 5 and 8 is 101 Please Enter Valid Input Lowest Common Ancestor of 5 and 10 is -1

C++ Implementation

#include<bits/stdc++.h> using namespace std;  // Node class class Node{ public: int val; Node *left, *right;  Node(int Val){ val = Val; left = nullptr; right = nullptr; } };  bool b1, b2; Node *findLCA(Node *node, int n1, int n2){ // Base case. if (node == nullptr) return nullptr;  Node *ans = nullptr;  if (node->val == n1){  b1 = true; ans = node; }  else if(node->val == n2){  b2 = true; ans = node; }  Node *leftAns = findLCA(node->left, n1, n2); Node *rightAns = findLCA(node->right, n1, n2);  if (ans != nullptr) return ans;  if (leftAns != nullptr && rightAns != nullptr) return node; return leftAns != nullptr ? leftAns : rightAns; }  int LCA(Node *root, int n1, int n2) { b1 = false; b2 = false; Node *lca = findLCA(root, n1, n2); if(b1 && b2){ return lca->val; } cout << "Please enter valid input" << endl; return -1; } int main() {  Node *root = new Node(1); root->left = new Node(2); root->left->left = new Node(4); root->left->left->right = new Node(7); root->left->right = new Node(5); root->right = new Node(3); root->right->right = new Node(6); root->right->right->left = new Node(8); root->right->right->right = new Node(9);  cout << "LCA of 4 and 5 is " << LCA (root, 4, 5) << endl; cout << "LCA of 7 and 4 is " << LCA (root, 7, 4) << endl; cout << "LCA of 5 and 8 is " << LCA (root, 5, 8) << endl; cout << "LCA of 5 and 10 is " << LCA (root, 5, 10) << endl; }

Output

LCA of 4 and 5 is 2 LCA of 7 and 4 is 4 LCA of 5 and 8 is 1 LCA of 5 and 10 is. Please enter valid input -1

Python Implementation

# Node class class Node: def __init__(self, value): self.value = value self.left = None self.right = None  boolean = [False]*2 def findLCA(node, n1, n2): if (node == None): return None  answer = None  if (node.value == n1):  boolean[0] = True answer = node  elif(node.value == n2):  boolean[1] = True answer = node  leftAns = findLCA(node.left, n1, n2) rightAns = findLCA(node.right, n1, n2)  if (answer != None): return answer if (leftAns != None and rightAns != None): return node if (leftAns != None): return leftAns else: return rightAns  def LCA(root, n1, n2): global boolean boolean = [False, False]  lca = findLCA(root, n1, n2)  if(boolean[0] and boolean[1]): return lca.value  print("Please enter valid input") return -1 root = Node(3) root.left = Node(8) root.left.left = Node(9) root.left.left.right = Node(10) root.left.right = Node(12) root.right = Node(32) root.right.right = Node(63) root.right.right.left = Node(89) root.right.right.right = Node(93)  print("Lowest common Ancestor of 3 and 9 is ", LCA (root, 3, 9)) print("Lowest Common Ancestor  of 10 and 12 is ", LCA (root, 10, 12)) print("Lowest common Ancestor of 32 and 89 is ", LCA (root, 32, 89)) print("Lowest common Ancestor of 63 and 93 is ", LCA (root, 63, 93))

Output

Lowest common Ancestor of 3 and 9 is  3 Lowest Common Ancestor  of 10 and 12 is  8 Lowest common Ancestor of 32 and 89 is  32 Lowest common Ancestor of 63 and 93 is  63

Complexity Analysis

Let’s see the complexity of this approach.

  • Time Complexity: This approach’s Time Complexity will be O(n) to find the LCA of a binary tree. After traversing the whole binary tree in the worst case.
  • Space Complexity: The height of the recursive tree can reach up to O(h), where h is the height of the binary tree. The overall space complexity of this algorithm is O(h).
DevOps & Cloud Engineering
Internship Assurance
DevOps & Cloud Engineering

Approach 3: Iterative Approach

In this approach, we will find the lowest common ancestor using the iterative approach. The main idea is to traverse the binary tree until we have found both of our target nodes, and then we will traverse back from the target node to the root using the Map data structure in this example. Let’s see the steps of this approach.

Algorithm

  • Before moving forward, we must define the HashMap in which they store both keys and values.
  • You also have to declare a queue of node type that will be used to traverse the in-level order fashion.
  • Traverse in level order until we have found both our target nodes. While tracing, we will make sure that we map the nodes with their parents using the Map we declared initially.
  • In the next step, we must move from the target1 to the root node and store the pat in a HashSet data structure.
  • The first node is part of the part from target2 to the root node. This node is present in the HashSet in our answer

Java Implementation

import java.util.*; class BinaryTree{ static int LowestCommonAncestor(Node root, int n1, int n2){ Map<Node,Node> parent  = new HashMap<>() ; Queue <Node> q = new LinkedList<>() ; parent.put(root,null) ; q.add(root) ;  Node x = null, y = null ; while(!q.isEmpty() && (x == null || y == null)){ Node node  = q.poll() ;  if(node.value == n1){ x = node ; }else if(node.value == n2){ y = node ; }  if(node.left != null){ parent.put(node.right,node) ; q.add(node.right) ; } }  if(x == null || y== null) return -1 ;  Set <Node> set = new HashSet<>();  while (x != null){ set.add(x) ; x =  parent.get(x) ; }  while(!set.contains(y)){ set.add(y) ; y = parent.get(y) ; }  return y.value ; } public static void main(String args[]){ Node root = new Node(1) ; root.left =  new Node(2) ; root.left.left = new Node(4) ; root.left.left.right = new Node(8) ; root.left.right = new Node(5) ; root.right = new Node(10) ; root.right.right = new Node(38) ; root.right.right.left = new Node(10) ; root.right.right.right = new Node(83) ;  System.out.println("Lowest common Ancestor 4 and 8  "+LowestCommonAncestor(root, 4, 8)) ; System.out.println("Lowest common Ancestor 7 and 4 "+LowestCommonAncestor(root, 8, 9)) ; System.out.println("Lowest common Ancestor 5 and 8 "+LowestCommonAncestor(root,5, 8)); System.out.println("Lowest common Ancestor 38 and 83"+LowestCommonAncestor(root,38,83)) ; } }  class Node{ int value ; Node left, right ; Node(int value){ this.value = value ; } }

Output

Lowest common Ancestor 4 and 8  -1 Lowest common Ancestor 7 and 4 -1 Lowest common Ancestor 5 and 8 -1 Lowest common Ancestor 38 and 83 -1

C++ Implementation

#include<bits/stdc++.h> using namespace std;  class Node{ public: int val; Node *left, *right;  Node(int Val){ val = Val; left = nullptr; right = nullptr; } };  int LCA(Node *root, int n1, int n2) { unordered_map<Node*, Node*> parent;  queue<Node*> q;  parent[root]= nullptr; q.push(root);  Node *x = nullptr, *y = nullptr;  while (!q.empty() && (x == nullptr || y == nullptr)){  Node *node = q.front(); q.pop(); if(node->val == n1){ x = node; } else if(node->val == n2){ y = node; }  if(node->left != nullptr){ parent[node->left] = node; q.push(node->left); } if(node->right != nullptr){ parent[node->right] = node; q.push(node->right); } } if (x == nullptr || y == nullptr) return -1;  unordered_set<Node*> set;  while (x != nullptr){ set.insert(x); x = parent[x]; }  while (set.find(y) == set.end()){ set.insert(y); y = parent[y]; }  return y->val; } int main() {  Node *root = new Node(34); root->left = new Node(33); root->left->left = new Node(50); root->left->left->right = new Node(60); root->left->right = new Node(70); root->right = new Node(80); root->right->right = new Node(89); root->right->right->left = new Node(92); root->right->right->right = new Node(97);  cout << "Lowest common ancestor of 34 and 50 is " << LCA (root, 34, 50) << endl; cout << "Lowest common ancestor of 60 and 80 is " << LCA (root, 60, 80) << endl; cout << "Lowest common ancestor of 50 and 92 is " << LCA (root, 50, 92) << endl;  }

Output

Lowest common ancestor of 34 and 50 is 34 Lowest common ancestor of 60 and 80 is 34 Lowest common ancestor of 50 and 92 is 34

Python Implementation

# Node class class Node: def __init__(self, val): self.val = val self.left = None self.right = None def LCA(root, n1, n2): parent = {}  q = []  parent[root] = None q.append(root)  x, y  = None, None  while (len(q) > 0 and (x == None or y == None)):  node = q.pop()  if(node.val == n1): x = node  elif(node.val == n2): y = node  if(node.left != None): parent[node.left] = node q.append(node.left)  if(node.right != None): parent[node.right] = node q.append(node.right)  if (x == None or y == None): return -1  Set = set()  while (x != None): Set.add(x) x = parent[x]  while y not in Set: Set.add(y) y = parent[y]  return y.val  root = Node(5) root.left = Node(23) root.left.left = Node(45) root.left.left.right = Node(78) root.left.right = Node(80) root.right = Node(85) root.right.right = Node(90) root.right.right.left = Node(93) root.right.right.right = Node(100)  print("Lowest Common Ancestor of 5 and 23 is ", LCA (root, 5, 23)) print("Lowest Common Ancestor of 23 and 78 is ", LCA (root, 23, 78)) print("Lowest Common Ancestor of 45 and 90 is ", LCA (root, 45, 90))

Output

Lowest Common Ancestor of 5 and 23 is  5 Lowest Common Ancestor of 23 and 78 is  23 Lowest Common Ancestor of 45 and 90 is  5

Complexity Analysis

Let’s describe the time and space complexity of the lowest common ancestor.

 

  • Time Complexity: In this approach, we must traverse the whole tee in the worst case, which costs O(n) time. The overall time complexity required to find the lowest common ancestor of a binary tree is O(n).
  • Space Complexity: The space complexity of traversing a binary tree in a lever order fashion, the size queue can reach up to O(n). The overall space complexity is O(n).

Conclusion

This article taught us “how to find the lowest common ancestor in a Binary Tree.” We see various approaches to this problem. A common and efficient approach is one of the best approaches to solve this problem by recursive approach. By Understanding this approach, developers can make programs more efficient and useful. The recursive approach makes the program a balance of efficiency and simplicity, making the recursive approach a preferred choice for finding the lowest common Ancestor in binary trees.

FAQs
The Lowest common ancestor of two nodes in the Binary tree is the deepest node, an ancestor of both nodes.
Yes, Finding the Lowest Common Ancestor of more than two nodes can be extended from the binary case by iteratively applying the Lowest Common Ancestor function on pairs of nodes.  This ensures the final result is the Lowest Common Ancestor of all the given nodes.
A Binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left and right child. It is a special case of a tree data structure in which every node has either 0, 1, or 2 children.
It can be found iteratively, but it is more complex than the recursive approach. The iterative approach involves using parent pointers to trace the paths from the nodes to the root and then finding the intersection of these paths.
brochureimg

The DevOps Playbook

Simplify deployment with Docker containers.

Streamline development with modern practices.

Enhance efficiency with automated workflows.

left dot patternright dot pattern

Programs tailored for your success

Popular

Management

Data Science

Finance

Technology

Future Tech

Upskill with expert articles

View all
Hero Vired logo
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance

Integrated Program in Finance and Financial Technologies

Certificate Program in Financial Analysis, Valuation and Risk Management

Management

Certificate Program in Strategic Management and Business Essentials

Executive Program in Product Management

Certificate Program in Product Management

Certificate Program in Technology-enabled Sales

Future Tech

Certificate Program in Gaming & Esports

Certificate Program in Extended Reality (VR+AR)

Professional Diploma in UX Design

Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
18003093939     ·     hello@herovired.com     ·    Whatsapp
Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved