Lowest Common Ancestor in a Binary Tree

Last Updated : 17 Apr, 2023

What is Lowest Common Ancestor in Binary Tree?

The lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants, where n1 and n2 are the nodes for which we wish to find the LCA. Hence, the LCA of a binary tree with nodes n1 and n2 is the shared ancestor of n1 and n2 that is located farthest from the root.

Application of Lowest Common Ancestor(LCA):

To determine the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor.

Lowest Common Ancestor in Binary Tree

Lowest Common Ancestor in a Binary Tree By Storing paths from root to n1 and root to n2:

The idea of this approach is to store the path from the root to n1 and root to n2 in two separate data structures. Then look simultaneously into the values stored in the data structure, and look for the first mismatch.

Illustration:

Find the LCA of 5 and 6

Path from root to 5 = { 1, 2, 5 }
Path from root to 6 = { 1, 3, 6 }

We start checking from 0 index. As both of the value matches( pathA[0] = pathB[0] ), we move to the next index.

pathA[1] not equals to pathB[1], there’s a mismatch so we consider the previous value.

Therefore the LCA of (5,6) = 1

Follow the steps below to solve the problem:

Find a path from the root to n1 and store it in a vector or array.
Find a path from the root to n2 and store it in another vector or array.
Traverse both paths till the values in arrays are the same. Return the common element just before the mismatch.

Following is the implementation of the above algorithm:

C++

// C++ Program for Lowest Common Ancestor 
// in a Binary Tree
// A O(n) solution to find LCA 
// of two given values n1 and n2
 
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree node
struct Node {
    int key;
    struct Node *left, *right;
};
 
// Utility function creates a new binary tree node with
// given key
Node* newNode(int k)
{
    Node* temp = new Node;
    temp->key = k;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Finds the path from root node to given root of the tree,
// Stores the path in a vector path[], returns true if path
// exists otherwise false
bool findPath(Node* root, vector<int>& path, int k)
{
    // base case
    if (root == NULL)
        return false;
 
    // Store this node in path vector. The node will be
    // removed if not in path from root to k
    path.push_back(root->key);
 
    // See if the k is same as root's key
    if (root->key == k)
        return true;
 
    // Check if k is found in left or right sub-tree
    if ((root->left && findPath(root->left, path, k))
        || (root->right && findPath(root->right, path, k)))
        return true;
 
    // If not present in subtree rooted with root, remove
    // root from path[] and return false
    path.pop_back();
    return false;
}
 
// Returns LCA if node n1, n2 are present in the given
// binary tree, otherwise return -1
int findLCA(Node* root, int n1, int n2)
{
    // to store paths to n1 and n2 from the root
    vector<int> path1, path2;
 
    // Find paths from root to n1 and root to n2. If either
    // n1 or n2 is not present, return -1
    if (!findPath(root, path1, n1)
        || !findPath(root, path2, n2))
        return -1;
 
    /* Compare the paths to get the first different value */
    int i;
    for (i = 0; i < path1.size() && i < path2.size(); i++)
        if (path1[i] != path2[i])
            break;
    return path1[i - 1];
}
 
// Driver program to test above functions
int main()
{
    // Let us create the Binary Tree shown in above diagram.
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout << "LCA(4, 5) = " << findLCA(root, 4, 5);
    cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6);
    cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4);
    cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4);
    return 0;
}

Java

// Java Program for Lowest Common Ancestor 
// in a Binary Tree
// A O(n) solution to find LCA of 
// two given values n1 and n2
 
import java.util.ArrayList;
import java.util.List;
 
// A Binary Tree node
class Node {
    int data;
    Node left, right;
 
    Node(int value)
    {
        data = value;
        left = right = null;
    }
}
 
public class BT_NoParentPtr_Solution1 {
 
    Node root;
    private List<Integer> path1 = new ArrayList<>();
    private List<Integer> path2 = new ArrayList<>();
 
    // Finds the path from root node to given root of the
    // tree.
    int findLCA(int n1, int n2)
    {
        path1.clear();
        path2.clear();
        return findLCAInternal(root, n1, n2);
    }
 
    private int findLCAInternal(Node root, int n1, int n2)
    {
 
        if (!findPath(root, n1, path1)
            || !findPath(root, n2, path2)) {
            System.out.println((path1.size() > 0)
                                   ? "n1 is present"
                                   : "n1 is missing");
            System.out.println((path2.size() > 0)
                                   ? "n2 is present"
                                   : "n2 is missing");
            return -1;
        }
 
        int i;
        for (i = 0; i < path1.size() && i < path2.size();
             i++) {
 
            // System.out.println(path1.get(i) + " " +
            // path2.get(i));
            if (!path1.get(i).equals(path2.get(i)))
                break;
        }
 
        return path1.get(i - 1);
    }
 
    // Finds the path from root node to given root of the
    // tree, Stores the path in a vector path[], returns
    // true if path exists otherwise false
    private boolean findPath(Node root, int n,
                             List<Integer> path)
    {
        // base case
        if (root == null) {
            return false;
        }
 
        // Store this node . The node will be removed if
        // not in path from root to n.
        path.add(root.data);
 
       if (root.data == n ||
            findPath(root.left, n, path) ||
            findPath(root.right, n, path)) {
            return true;
        }
 
        // If not present in subtree rooted with root,
        // remove root from path[] and return false
        path.remove(path.size() - 1);
 
        return false;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        BT_NoParentPtr_Solution1 tree
            = new BT_NoParentPtr_Solution1();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
 
        System.out.println("LCA(4, 5) = "
                           + tree.findLCA(4, 5));
        System.out.println("LCA(4, 6) = "
                           + tree.findLCA(4, 6));
        System.out.println("LCA(3, 4) = "
                           + tree.findLCA(3, 4));
        System.out.println("LCA(2, 4) = "
                           + tree.findLCA(2, 4));
    }
}
// This code is contributed by Sreenivasulu Rayanki.

Python3

# Python Program for Lowest Common Ancestor in a Binary Tree
# O(n) solution to find LCS of two given values n1 and n2
 
# A binary tree node
class Node:
    # Constructor to create a new binary node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
# Finds the path from root node to given root of the tree.
# Stores the path in a list path[], returns true if path
# exists otherwise false
def findPath(root, path, k):
 
    # Baes Case
    if root is None:
        return False
 
    # Store this node is path vector. The node will be
    # removed if not in path from root to k
    path.append(root.key)
 
    # See if the k is same as root's key
    if root.key == k:
        return True
 
    # Check if k is found in left or right sub-tree
    if ((root.left != None and findPath(root.left, path, k)) or
            (root.right != None and findPath(root.right, path, k))):
        return True
 
    # If not present in subtree rooted with root, remove
    # root from path and return False
 
    path.pop()
    return False
 
# Returns LCA if node n1 , n2 are present in the given
# binary tree otherwise return -1
def findLCA(root, n1, n2):
 
    # To store paths to n1 and n2 fromthe root
    path1 = []
    path2 = []
 
    # Find paths from root to n1 and root to n2.
    # If either n1 or n2 is not present , return -1
    if (not findPath(root, path1, n1) or not findPath(root, path2, n2)):
        return -1
 
    # Compare the paths to get the first different value
    i = 0
    while(i < len(path1) and i < len(path2)):
        if path1[i] != path2[i]:
            break
        i += 1
    return path1[i-1]
 
 
# Driver program to test above function
if __name__ == '__main__':
     
    # Let's create the Binary Tree shown in above diagram
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
     
    print("LCA(4, 5) = %d" % (findLCA(root, 4, 5,)))
    print("LCA(4, 6) = %d" % (findLCA(root, 4, 6)))
    print("LCA(3, 4) = %d" % (findLCA(root, 3, 4)))
    print("LCA(2, 4) = %d" % (findLCA(root, 2, 4)))
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# Program for Lowest Common
// Ancestor in a Binary Tree
// A O(n) solution to find LCA
// of two given values n1 and n2
using System.Collections;
using System;
 
// A Binary Tree node
class Node {
    public int data;
    public Node left, right;
 
    public Node(int value)
    {
        data = value;
        left = right = null;
    }
}
 
public class BT_NoParentPtr_Solution1 {
 
    Node root;
    private ArrayList path1 = new ArrayList();
    private ArrayList path2 = new ArrayList();
 
    // Finds the path from root
    // node to given root of the
    // tree.
    int findLCA(int n1, int n2)
    {
        path1.Clear();
        path2.Clear();
        return findLCAInternal(root, n1, n2);
    }
 
    private int findLCAInternal(Node root, int n1, int n2)
    {
        if (!findPath(root, n1, path1)
            || !findPath(root, n2, path2)) {
            Console.Write((path1.Count > 0)
                              ? "n1 is present"
                              : "n1 is missing");
            Console.Write((path2.Count > 0)
                              ? "n2 is present"
                              : "n2 is missing");
            return -1;
        }
 
        int i;
        for (i = 0; i < path1.Count && i < path2.Count;
             i++) {
            // System.out.println(path1.get(i)
            // + " " + path2.get(i));
            if ((int)path1[i] != (int)path2[i])
                break;
        }
        return (int)path1[i - 1];
    }
 
    // Finds the path from root node
    // to given root of the tree,
    // Stores the path in a vector
    // path[], returns true if path
    // exists otherwise false
    private bool findPath(Node root, int n, ArrayList path)
    {
        // base case
        if (root == null) {
            return false;
        }
 
        // Store this node . The node
        // will be removed if not in
        // path from root to n.
        path.Add(root.data);
 
        if (root.data == n) {
            return true;
        }
 
        if (root.left != null
            && findPath(root.left, n, path)) {
            return true;
        }
 
        if (root.right != null
            && findPath(root.right, n, path)) {
            return true;
        }
 
        // If not present in subtree
        // rooted with root, remove root
        // from path[] and return false
        path.RemoveAt(path.Count - 1);
 
        return false;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        BT_NoParentPtr_Solution1 tree
            = new BT_NoParentPtr_Solution1();
 
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
 
        Console.Write("LCA(4, 5) = " + tree.findLCA(4, 5));
        Console.Write("\nLCA(4, 6) = "
                      + tree.findLCA(4, 6));
        Console.Write("\nLCA(3, 4) = "
                      + tree.findLCA(3, 4));
        Console.Write("\nLCA(2, 4) = "
                      + tree.findLCA(2, 4));
    }
}
 
// This code is contributed by Rutvik_56

Javascript

<script>
 
    // JavaScript Program for Lowest Common 
    // Ancestor in a Binary Tree
    // A O(n) solution to find LCA of 
    // two given values n1 and n2
     
    class Node
    {
        constructor(value) {
           this.left = null;
           this.right = null;
           this.data = value;
        }
    }
     
    let root;
    let path1 = [];
    let path2 = [];
  
    // Finds the path from root node to given root of the tree.
    function findLCA(n1, n2) {
        path1 = [];
        path2 = [];
        return findLCAInternal(root, n1, n2);
    }
  
    function findLCAInternal(root, n1, n2) {
  
        if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) 
        {
            document.write((path1.length > 0) ? 
            "n1 is present" : "n1 is missing");
            document.write((path2.length > 0) ? 
            "n2 is present" : "n2 is missing");
            return -1;
        }
  
        let i;
        for (i = 0; i < path1.length && i < path2.length; i++) {
              
        // System.out.println(path1.get(i) + " " + path2.get(i));
            if (path1[i] != path2[i])
                break;
        }
  
        return path1[i-1];
    }
      
    // Finds the path from root node to 
    // given root of the tree, Stores the
    // path in a vector path[], returns true
    // if path exists otherwise false
    function findPath(root, n, path)
    {
        // base case
        if (root == null) {
            return false;
        }
          
        // Store this node . The node will be removed if
        // not in path from root to n.
        path.push(root.data);
  
        if (root.data == n) {
            return true;
        }
  
        if (root.left != null && findPath(root.left, n, path)) {
            return true;
        }
  
        if (root.right != null && findPath(root.right, n, path)) {
            return true;
        }
  
        // If not present in subtree rooted with root, 
        // remove root from
        // path[] and return false
        path.pop();
  
        return false;
    }
     
    root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
 
    document.write("LCA(4, 5) = " + findLCA(4,5) + "</br>");
    document.write("LCA(4, 6) = " + findLCA(4,6) + "</br>");
    document.write("LCA(3, 4) = " + findLCA(3,4) + "</br>");
    document.write("LCA(2, 4) = " + findLCA(2,4));
 
</script>

Output

LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2

Time Complexity: O(N). The tree is traversed twice, and then path arrays are compared.
Auxiliary Space: O(N). Extra Space for path1 and path2.

Lowest Common Ancestor in a Binary Tree By Single Traversal:

The idea is to traverse the tree starting from the root. If any of the given keys (n1 and n2) matches with the root, then the root is LCA (assuming that both keys are present). If the root doesn’t match with any of the keys, we recur for the left and right subtree.

The node which has one key present in its left subtree and the other key present in the right subtree is the LCA.

If both keys lie in the left subtree, then the left subtree has LCA also,

Otherwise, LCA lies in the right subtree.

Illustration:

Find the LCA of 5 and 6

Root is pointing to the node with value 1, as its value doesn’t match with { 5, 6 }. We look for the key in left subtree and right subtree.

Left Subtree :

New Root = { 2 } ≠ 5 or 6, hence we will continue our recursion

New Root = { 4 } , it’s left and right subtree is null, we will return NULL for this call

New Root = { 5 } , value matches with 5 so will return the node with value 5

The function call for root with value 2 will return a value of 5

Right Subtree :

Root = { 3 } ≠ 5 or 6 hence we continue our recursion

Root = { 6 } = 5 or 6 , we will return the this node with value 6

Root = { 7 } ≠ 5 or 6, we will return NULL

So the function call for root with value 3 will return node with value 6

As both the left subtree and right subtree of the node with value 1 is not NULL, so 1 is the LCA

Follow the steps below to solve the problem:

We pass the root to a helper function and check if the value of the root matches any of n1 and n2.
- If YES, return the root
- else recursive call on the left and right subtree
Basically, we do pre-order traversal, at first we check if the root->value matches with n1 or n2. Then traverse on the left and right subtree.
If there is any root that returns one NULL and another NON-NULL value, we shall return the corresponding NON-NULL value for that node.
The node that returns both NON-NULL values for both the left and right subtree, is our Lowest Common Ancestor.

Below is the implementation of the above approach.

C++

/* C++ Program to find LCA of n1 and n2 using one traversal
 * of Binary Tree */
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node {
    struct Node *left, *right;
    int key;
};
 
// Utility function to create a new tree Node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// This function returns pointer to LCA of two given values
// n1 and n2. This function assumes that n1 and n2 are
// present in Binary Tree
struct Node* findLCA(struct Node* root, int n1, int n2)
{
    // Base case
    if (root == NULL)
        return NULL;
 
    // If either n1 or n2 matches with root's key, report
    // the presence by returning root (Note that if a key is
    // ancestor of other, then the ancestor key becomes LCA
    if (root->key == n1 || root->key == n2)
        return root;
 
    // Look for keys in left and right subtrees
    Node* left_lca = findLCA(root->left, n1, n2);
    Node* right_lca = findLCA(root->right, n1, n2);
 
    // If both of the above calls return Non-NULL, then one
    // key is present in once subtree and other is present
    // in other, So this node is the LCA
    if (left_lca && right_lca)
        return root;
 
    // Otherwise check if left subtree or right subtree is
    // LCA
    return (left_lca != NULL) ? left_lca : right_lca;
}
 
// Driver program to test above functions
int main()
{
    // Let us create binary tree given in the above example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout << "LCA(4, 5) = " << findLCA(root, 4, 5)->key;
    cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6)->key;
    cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4)->key;
    cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4)->key;
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C Program to find LCA of n1 and n2 using one traversalof
// Binary Tree
#include <stdio.h>
#include <stdlib.h>
 
// A Binary Tree Node
typedef struct Node {
    struct Node *left, *right;
    int key;
} Node;
 
// Utility function to create a new tree Node
Node* newNode(int key)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// This function returns pointer to LCA of two given values
// n1 and n2. This function assumes that n1 and n2 are
// present in Binary Tree
Node* findLCA(Node* root, int n1, int n2)
{
    // Base case
    if (root == NULL)
        return NULL;
 
    // If either n1 or n2 matches with root's key, report
    // the presence by returning root (Note that if a key is
    // ancestor of other, then the ancestor key becomes LCA
    if (root->key == n1 || root->key == n2)
        return root;
 
    // Look for keys in left and right subtrees
    Node* left_lca = findLCA(root->left, n1, n2);
    Node* right_lca = findLCA(root->right, n1, n2);
 
    // If both of the above calls return Non-NULL, then one
    // key is present in once subtree and other is present
    // in other, So this node is the LCA
    if (left_lca && right_lca)
        return root;
 
    // Otherwise check if left subtree or right subtree is
    // LCA
    return (left_lca != NULL) ? left_lca : right_lca;
}
 
// Driver program to test above functions
int main()
{
    // Let us create binary tree given in the above example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    printf("LCA(4, 5) = %d", findLCA(root, 4, 5)->key);
    printf("\nLCA(4, 6) = %d", findLCA(root, 4, 6)->key);
    printf("\nLCA(3, 4) = %d", findLCA(root, 3, 4)->key);
    printf("\nLCA(2, 4) = %d", findLCA(root, 2, 4)->key);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree
 
/* Class containing left and right child of current
 node and key value*/
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    // Root of the Binary Tree
    Node root;
 
    Node findLCA(int n1, int n2)
    {
        return findLCA(root, n1, n2);
    }
 
    // This function returns pointer to LCA of two given
    // values n1 and n2. This function assumes that n1 and
    // n2 are present in Binary Tree
    Node findLCA(Node node, int n1, int n2)
    {
        // Base case
        if (node == null)
            return null;
 
        // If either n1 or n2 matches with root's key,
        // report the presence by returning root (Note that
        // if a key is ancestor of other, then the ancestor
        // key becomes LCA
        if (node.data == n1 || node.data == n2)
            return node;
 
        // Look for keys in left and right subtrees
        Node left_lca = findLCA(node.left, n1, n2);
        Node right_lca = findLCA(node.right, n1, n2);
 
        // If both of the above calls return Non-NULL, then
        // one key is present in once subtree and other is
        // present in other, So this node is the LCA
        if (left_lca != null && right_lca != null)
            return node;
 
        // Otherwise check if left subtree or right subtree
        // is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }
 
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        System.out.println("LCA(4, 5) = "
                           + tree.findLCA(4, 5).data);
        System.out.println("LCA(4, 6) = "
                           + tree.findLCA(4, 6).data);
        System.out.println("LCA(3, 4) = "
                           + tree.findLCA(3, 4).data);
        System.out.println("LCA(2, 4) = "
                           + tree.findLCA(2, 4).data);
    }
}

Python3

# Python program to find LCA of n1 and n2 using one
# traversal of Binary tree
 
# A binary tree node
 
 
class Node:
 
    # Constructor to create a new tree node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
# This function returns pointer to LCA of two given
# values n1 and n2
# This function assumes that n1 and n2 are present in
# Binary Tree
 
 
def findLCA(root, n1, n2):
 
    # Base Case
    if root is None:
        return None
 
    # If either n1 or n2 matches with root's key, report
    #  the presence by returning root (Note that if a key is
    #  ancestor of other, then the ancestor key becomes LCA
    if root.key == n1 or root.key == n2:
        return root
 
    # Look for keys in left and right subtrees
    left_lca = findLCA(root.left, n1, n2)
    right_lca = findLCA(root.right, n1, n2)
 
    # If both of the above calls return Non-NULL, then one key
    # is present in once subtree and other is present in other,
    # So this node is the LCA
    if left_lca and right_lca:
        return root
 
    # Otherwise check if left subtree or right subtree is LCA
    return left_lca if left_lca is not None else right_lca
 
 
# Driver code
if __name__ == '__main__':
     
    # Let us create a binary tree given in the above example
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    print("LCA(4, 5) = ", findLCA(root, 4, 5).key)
    print("LCA(4, 6) = ", findLCA(root, 4, 6).key)
    print("LCA(3, 4) = ", findLCA(root, 3, 4).key)
    print("LCA(2, 4) = ", findLCA(root, 2, 4).key)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# implementation to find lowest common
// ancestor of n1 and n2 using one traversal
// of binary tree
using System;
 
// Class containing left and right
// child of current node and key value
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
 
    // Root of the Binary Tree
    Node root;
 
    Node findLCA(int n1, int n2)
    {
        return findLCA(root, n1, n2);
    }
 
    // This function returns pointer to LCA
    // of two given values n1 and n2. This
    // function assumes that n1 and n2 are
    // present in Binary Tree
    Node findLCA(Node node, int n1, int n2)
    {
 
        // Base case
        if (node == null)
            return null;
 
        // If either n1 or n2 matches with
        // root's key, report the presence
        // by returning root (Note that if
        // a key is ancestor of other,
        // then the ancestor key becomes LCA
        if (node.data == n1 || node.data == n2)
            return node;
 
        // Look for keys in left and right subtrees
        Node left_lca = findLCA(node.left, n1, n2);
        Node right_lca = findLCA(node.right, n1, n2);
 
        // If both of the above calls return Non-NULL,
        // then one key is present in once subtree
        // and other is present in other, So this
        // node is the LCA
        if (left_lca != null && right_lca != null)
            return node;
 
        // Otherwise check if left subtree or
        // right subtree is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
 
        Console.WriteLine("LCA(4, 5) = "
                          + tree.findLCA(4, 5).data);
        Console.WriteLine("LCA(4, 6) = "
                          + tree.findLCA(4, 6).data);
        Console.WriteLine("LCA(3, 4) = "
                          + tree.findLCA(3, 4).data);
        Console.WriteLine("LCA(2, 4) = "
                          + tree.findLCA(2, 4).data);
    }
}
 
// This code is contributed by pratham76

Javascript

<script>
 
    // JavaScript implementation to find
    // lowest common ancestor of
    // n1 and n2 using one traversal of binary tree
     
    class Node
    {
        constructor(item) {
           this.left = null;
           this.right = null;
           this.data = item;
        }
    }
     
    //Root of the Binary Tree
    let root;
  
    function findlCA(n1, n2)
    {
        return findLCA(root, n1, n2);
    }
  
    // This function returns pointer to LCA of two given
    // values n1 and n2. This function assumes that n1 and
    // n2 are present in Binary Tree
    function findLCA(node, n1, n2)
    {
        // Base case
        if (node == null)
            return null;
  
        // If either n1 or n2 matches with root's key, report
        // the presence by returning root (Note that if a key is
        // ancestor of other, then the ancestor key becomes LCA
        if (node.data == n1 || node.data == n2)
            return node;
  
        // Look for keys in left and right subtrees
        let left_lca = findLCA(node.left, n1, n2);
        let right_lca = findLCA(node.right, n1, n2);
  
        // If both of the above calls return Non-NULL, then one key
        // is present in once subtree and other is present in other,
        // So this node is the LCA
        if (left_lca!=null && right_lca!=null)
            return node;
  
        // Otherwise check if left subtree or right subtree is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }
     
    root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    document.write("LCA(4, 5) = " +
                       findlCA(4, 5).data + "</br>");
    document.write("LCA(4, 6) = " +
                       findlCA(4, 6).data + "</br>");
    document.write("LCA(3, 4) = " +
                       findlCA(3, 4).data + "</br>");
    document.write("LCA(2, 4) = " +
                       findlCA(2, 4).data + "</br>");
     
</script>

Output

LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2

Time Complexity: O(N) as the method does a simple tree traversal in a bottom-up fashion.
Auxiliary Space: O(H), where H is the height of the tree.

Note: The above method assumes that keys are present in Binary Tree. If one key is present and the other is absent, then it returns the present key as LCA (Ideally should have returned NULL). We can extend this method to handle all cases by checking if n1 and n2 are present in the tree first and then finding the LCA of n1 and n2. To check whether the node is present in the binary tree or not then traverse on the tree for both n1 and n2 nodes separately.

C++

/* C++ program to find LCA of n1 and n2 using one traversal
   of Binary Tree. It handles all cases even when n1 or n2
   is not there in Binary Tree */
 
#include <iostream>
using namespace std;
 
// A Binary Tree Node
struct Node {
    struct Node *left, *right;
    int key;
};
 
// Utility function to create a new tree Node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// This function returns pointer to LCA of two given
// valuesn1 and n2.
struct Node* findLCAUtil(struct Node* root, int n1, int n2)
{
    // Base case
    if (root == NULL)
        return NULL;
 
    // If either n1 or n2 matches with root's key, report
    // the presence by returning root
    if (root->key == n1 || root->key == n2)
        return root;
 
    // Look for keys in left and right subtrees
    Node* left_lca = findLCAUtil(root->left, n1, n2);
    Node* right_lca = findLCAUtil(root->right, n1, n2);
 
    // If both of the above calls return Non-NULL nodes,
    // then one key is present in once subtree and other is
    // present in other, So this node is the LCA
    if (left_lca and right_lca)
        return root;
 
    // Otherwise check if left subtree or right subtree is
    // LCA
    return (left_lca != NULL) ? left_lca : right_lca;
}
 
// Returns true if key k is present in tree rooted with root
bool find(Node* root, int k)
{
    // Base Case
    if (root == NULL)
        return false;
 
    // If key is present at root, or in left subtree or
    // right subtree, return true;
    if (root->key == k || find(root->left, k)
        || find(root->right, k))
        return true;
 
    // Else return false
    return false;
}
 
// This function returns LCA of n1 and n2 only if both n1
// and n2 are present in tree, otherwise returns NULL;
Node* findLCA(Node* root, int n1, int n2)
{
    // Return LCA only if both n1 and n2 are present in tree
    if (find(root, n1) and find(root, n2))
        return findLCAUtil(root, n1, n2);
 
    // Else return NULL
    return NULL;
}
 
// Driver program to test above functions
int main()
{
    // Let us create a binary tree given in the above
    // example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
 
    Node* lca = findLCA(root, 4, 5);
 
    if (lca != NULL)
        cout << "LCA(4, 5) = " << lca->key;
    else
        cout << "Keys are not present ";
 
    lca = findLCA(root, 4, 10);
 
    if (lca != NULL)
        cout << "\nLCA(4, 10) = " << lca->key;
    else
        cout << "\nKeys are not present ";
 
    return 0;
}
 
// This code is contributed by Kshitij Dwivedi
// (kshitijdwivedi28)

Java

// Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree
// It also handles cases even when n1 and n2 are not there
// in Tree
 
/* Class containing left and right child of current node and
 * key */
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    // Root of the Binary Tree
    Node root;
    static boolean v1 = false, v2 = false;
 
    // This function returns pointer to LCA of two given
    // values n1 and n2.
    // v1 is set as true by this function if n1 is found
    // v2 is set as true by this function if n2 is found
    Node findLCAUtil(Node node, int n1, int n2)
    {
        // Base case
        if (node == null)
            return null;
 
        // Store result in temp, in case of key match so
        // that we can search for other key also.
        Node temp = null;
 
        // If either n1 or n2 matches with root's key,
        // report the presence by setting v1 or v2 as true
        // and return root (Note that if a key is ancestor
        // of other, then the ancestor key becomes LCA)
        if (node.data == n1) {
            v1 = true;
            temp = node;
        }
        if (node.data == n2) {
            v2 = true;
            temp = node;
        }
 
        // Look for keys in left and right subtrees
        Node left_lca = findLCAUtil(node.left, n1, n2);
        Node right_lca = findLCAUtil(node.right, n1, n2);
 
        if (temp != null)
            return temp;
 
        // If both of the above calls return Non-NULL, then
        // one key is present in once subtree and other is
        // present in other, So this node is the LCA
        if (left_lca != null && right_lca != null)
            return node;
 
        // Otherwise check if left subtree or right subtree
        // is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }
 
    // Finds lca of n1 and n2 under the subtree rooted with
    // 'node'
    Node findLCA(int n1, int n2)
    {
        // Initialize n1 and n2 as not visited
        v1 = false;
        v2 = false;
 
        // Find lca of n1 and n2 using the technique
        // discussed above
        Node lca = findLCAUtil(root, n1, n2);
 
        // Return LCA only if both n1 and n2 are present in
        // tree
        if (v1 && v2)
            return lca;
 
        // Else return NULL
        return null;
    }
 
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
 
        Node lca = tree.findLCA(4, 5);
        if (lca != null)
            System.out.println("LCA(4, 5) = " + lca.data);
        else
            System.out.println("Keys are not present");
 
        lca = tree.findLCA(4, 10);
        if (lca != null)
            System.out.println("LCA(4, 10) = " + lca.data);
        else
            System.out.println("Keys are not present");
    }
}

Python3

""" Program to find LCA of n1 and n2 using one traversal of
 Binary tree
It handles all cases even when n1 or n2 is not there in tree
"""
 
# A binary tree node
 
 
class Node:
 
    # Constructor to create a new node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
# This function return pointer to LCA of two given values
# n1 and n2
# v1 is set as true by this function if n1 is found
# v2 is set as true by this function if n2 is found
 
 
def findLCAUtil(root, n1, n2, v):
 
    # Base Case
    if root is None:
        return None
 
    # IF either n1 or n2 matches ith root's key, report
    # the presence by setting v1 or v2 as true and return
    # root (Note that if a key is ancestor of other, then
    # the ancestor key becomes LCA)
    if root.key == n1:
        v[0] = True
        return root
 
    if root.key == n2:
        v[1] = True
        return root
 
    # Look for keys in left and right subtree
    left_lca = findLCAUtil(root.left, n1, n2, v)
    right_lca = findLCAUtil(root.right, n1, n2, v)
 
    # If both of the above calls return Non-NULL, then one key
    # is present in once subtree and other is present in other,
    # So this node is the LCA
    if left_lca and right_lca:
        return root
 
    # Otherwise check if left subtree or right subtree is LCA
    return left_lca if left_lca is not None else right_lca
 
 
def find(root, k):
 
    # Base Case
    if root is None:
        return False
 
    # If key is present at root, or if left subtree or right
    # subtree , return true
    if (root.key == k or find(root.left, k) or
            find(root.right, k)):
        return True
 
    # Else return false
    return False
 
# This function returns LCA of n1 and n2 on value if both
# n1 and n2 are present in tree, otherwise returns None
 
 
def findLCA(root, n1, n2):
 
    # Initialize n1 and n2 as not visited
    v = [False, False]
 
    # Find lca of n1 and n2 using the technique discussed above
    lca = findLCAUtil(root, n1, n2, v)
 
    # Returns LCA only if both n1 and n2 are present in tree
    if (v[0] and v[1] or v[0] and find(lca, n2) or v[1] and
            find(lca, n1)):
        return lca
 
    # Else return None
    return None
 
 
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
 
lca = findLCA(root, 4, 5)
 
if lca is not None:
    print("LCA(4, 5) = ", lca.key)
else:
    print("Keys are not present")
 
lca = findLCA(root, 4, 10)
if lca is not None:
    print("LCA(4,10) = ", lca.key)
else:
    print("Keys are not present")
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

using System;
 
// c# implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree
// It also handles cases even when n1 and n2 are not there
// in Tree
 
/* Class containing left and right child of current node and
 * key */
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    // Root of the Binary Tree
    public Node root;
    public static bool v1 = false, v2 = false;
 
    // This function returns pointer to LCA of two given
    // values n1 and n2.
    // v1 is set as true by this function if n1 is found
    // v2 is set as true by this function if n2 is found
    public virtual Node findLCAUtil(Node node, int n1,
                                    int n2)
    {
        // Base case
        if (node == null) {
            return null;
        }
 
        // Store result in temp, in case of key match so
        // that we can search for other key also.
        Node temp = null;
 
        // If either n1 or n2 matches with root's key,
        // report the presence by setting v1 or v2 as true
        // and return root (Note that if a key is ancestor
        // of other, then the ancestor key becomes LCA)
        if (node.data == n1) {
            v1 = true;
            temp = node;
        }
        if (node.data == n2) {
            v2 = true;
            temp = node;
        }
 
        // Look for keys in left and right subtrees
        Node left_lca = findLCAUtil(node.left, n1, n2);
        Node right_lca = findLCAUtil(node.right, n1, n2);
 
        if (temp != null) {
            return temp;
        }
 
        // If both of the above calls return Non-NULL, then
        // one key is present in once subtree and other is
        // present in other, So this node is the LCA
        if (left_lca != null && right_lca != null) {
            return node;
        }
 
        // Otherwise check if left subtree or right subtree
        // is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }
 
    // Finds lca of n1 and n2 under the subtree rooted with
    // 'node'
    public virtual Node findLCA(int n1, int n2)
    {
        // Initialize n1 and n2 as not visited
        v1 = false;
        v2 = false;
 
        // Find lca of n1 and n2 using the technique
        // discussed above
        Node lca = findLCAUtil(root, n1, n2);
 
        // Return LCA only if both n1 and n2 are present in
        // tree
        if (v1 && v2) {
            return lca;
        }
 
        // Else return NULL
        return null;
    }
 
    /* Driver program to test above functions */
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
 
        Node lca = tree.findLCA(4, 5);
        if (lca != null) {
            Console.WriteLine("LCA(4, 5) = " + lca.data);
        }
        else {
            Console.WriteLine("Keys are not present");
        }
 
        lca = tree.findLCA(4, 10);
        if (lca != null) {
            Console.WriteLine("LCA(4, 10) = " + lca.data);
        }
        else {
            Console.WriteLine("Keys are not present");
        }
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// JavaScript implementation to find lowest 
// common ancestor of n1 and n2 using one
// traversal of binary tree. It also handles 
// cases even when n1 and n2 are not there in Tree
 
// Class containing left and right child 
// of current node and key 
class Node 
{
    constructor(item)
    {
        this.data = item;
        this.left = null;
        this.right = null;
    }
}
 
class BinaryTree{
     
// Root of the Binary Tree
constructor() 
{
    this.root = null;
    this.v1 = false;
    this.v2 = false;
}
 
// This function returns pointer to LCA 
// of two given values n1 and n2.
// v1 is set as true by this function 
// if n1 is found
// v2 is set as true by this function
// if n2 is found
findLCAUtil(node, n1, n2)
{
     
    // Base case
    if (node == null) 
    {
        return null;
    }
     
    // Store result in temp, in case of 
    // key match so that we can search
    // for other key also.
    var temp = null;
     
    // If either n1 or n2 matches with root's key,
    // report the presence by setting v1 or v2 as
    // true and return root (Note that if a key
    // is ancestor of other, then the ancestor 
    // key becomes LCA)
    if (node.data == n1) 
    {
        this.v1 = true;
        temp = node;
    }
    if (node.data == n2) 
    {
        this.v2 = true;
        temp = node;
    }
     
    // Look for keys in left and right subtrees
    var left_lca = this.findLCAUtil(node.left, n1, n2);
    var right_lca = this.findLCAUtil(node.right, n1, n2);
     
    if (temp != null)
    {
        return temp;
    }
     
    // If both of the above calls return Non-NULL, 
    // then one key is present in once subtree and 
    // other is present in other, So this node is the LCA
    if (left_lca != null && right_lca != null) 
    {
        return node;
    }
     
    // Otherwise check if left subtree or 
    // right subtree is LCA
    return left_lca != null ? left_lca : right_lca;
}
 
// Finds lca of n1 and n2 under the
// subtree rooted with 'node'
findLCA(n1, n2)
{
     
    // Initialize n1 and n2 as not visited
    this.v1 = false;
    this.v2 = false;
     
    // Find lca of n1 and n2 using the
    // technique discussed above
    var lca = this.findLCAUtil(this.root, n1, n2);
     
    // Return LCA only if both n1 and n2 
    // are present in tree
    if (this.v1 && this.v2) 
    {
        return lca;
    }
     
    // Else return NULL
    return null;
}
}
 
// Driver code
var tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
 
var lca = tree.findLCA(4, 5);
if (lca != null) 
{
    document.write("LCA(4, 5) = " +
                   lca.data + "<br>");
} else
{
    document.write("Keys are not present" + "<br>");
}
 
lca = tree.findLCA(4, 10);
if (lca != null) 
{
    document.write("LCA(4, 10) = " + 
                   lca.data + "<br>");
} 
else
{
    document.write("Keys are not present" + "<br>");
}
 
// This code is contributed by rdtank
 
</script>

Output

LCA(4, 5) = 2
Keys are not present

Time Complexity: O(N) as the method does a simple tree traversal in a bottom-up fashion.
Auxiliary Space: O(H), where h is the height of the tree.

Using an Auxiliary data structure (hash table):

The basic idea behind the "Using an auxiliary data structure" approach for finding the lowest common ancestor of two nodes in a binary tree is to use a hash table or a map to store the parent pointers of each node. Once we have the parent pointers, we can traverse up from the first node and add all its ancestors to a set or a list. Then we can traverse up from the second node and check if each ancestor is already in the set or the list. The first ancestor that is already in the set or the list is the lowest common ancestor.

Follow the steps to implement the above approach:

Create a hash table or a map to store the parent pointers of each node in the binary tree.
Traverse the binary tree and populate the hash table or the map with the parent pointers for each node.
Starting from the first node, traverse up the tree and add each ancestor to a set or a list.
Starting from the second node, traverse up the tree and check if each ancestor is already in the set or the list. The first ancestor that is already in the set or the list is the lowest common ancestor.
If no common ancestor is found, return null or any other value that indicates the absence of a common ancestor.

Below is the implementation for the above approach:

C++

// C++ code to implement above approach
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
// Definition of a binary tree node
struct Node {
    int data;
    Node* left;
    Node* right;
};
 
// Function to create a new binary tree node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
 
// Function to build a hash table or a map of parent
// pointers for each node in the tree
unordered_map<Node*, Node*> buildParentMap(Node* root)
{
    unordered_map<Node*, Node*> parentMap;
    parentMap[root] = NULL;
    vector<Node*> queue = { root };
    while (!queue.empty()) {
        Node* node = queue.front();
        queue.erase(queue.begin());
        if (node->left) {
            parentMap[node->left] = node;
            queue.push_back(node->left);
        }
        if (node->right) {
            parentMap[node->right] = node;
            queue.push_back(node->right);
        }
    }
    return parentMap;
}
 
// Function to find the lowest common ancestor of two nodes
// using an auxiliary data structure
int findLCA(Node* root, int n1, int n2)
{
    // Build a hash table or a map of parent pointers for
    // each node in the tree
    unordered_map<Node*, Node*> parentMap
        = buildParentMap(root);
 
    // Find the nodes with values n1 and n2
    Node* p = NULL;
    Node* q = NULL;
    vector<Node*> queue = { root };
    while (!queue.empty()) {
        Node* node = queue.front();
        queue.erase(queue.begin());
        if (node->data == n1) {
            p = node;
        }
        if (node->data == n2) {
            q = node;
        }
        if (node->left) {
            queue.push_back(node->left);
        }
        if (node->right) {
            queue.push_back(node->right);
        }
    }
 
    // Add all the ancestors of the first node to a set or a
    // list
    set<Node*> ancestors;
    while (p) {
        ancestors.insert(p);
        p = parentMap[p];
    }
 
    // Traverse up from the second node and check if each
    // ancestor is already in the set or the list
    while (q) {
        if (ancestors.find(q) != ancestors.end()) {
            return q
                ->data; // The first ancestor that is
                        // already in the set or the list is
                        // the lowest common ancestor
        }
        q = parentMap[q];
    }
 
    return -1; // No common ancestor found
}
 
// Driver code
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
 
    cout << "LCA(4, 5) = " << findLCA(root, 4, 5) << endl;
    cout << "LCA(4, 6) = " << findLCA(root, 4, 6) << endl;
    cout << "LCA(3,4) = " << findLCA(root, 3, 4) << endl;
    cout << "LCA(2, 4) = " << findLCA(root, 2, 4) << endl;
 
    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot

Java

import java.util.*;
 
// Definition of a binary tree node
class Node {
  int data;
  Node left, right;
 
  public Node(int item)
  {
    data = item;
    left = right = null;
  }
}
 
class Main {
  // Function to build a hash table or a map of parent
  // pointers for each node in the tree
  static Map<Node, Node> buildParentMap(Node root)
  {
    Map<Node, Node> parentMap = new HashMap<>();
    parentMap.put(root, null);
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
      Node node = queue.poll();
      if (node.left != null) {
        parentMap.put(node.left, node);
        queue.add(node.left);
      }
      if (node.right != null) {
        parentMap.put(node.right, node);
        queue.add(node.right);
      }
    }
    return parentMap;
  }
 
  // Function to find the lowest common ancestor of two
  // nodes using an auxiliary data structure
  static int findLCA(Node root, int n1, int n2)
  {
    // Build a hash table or a map of parent pointers
    // for each node in the tree
    Map<Node, Node> parentMap = buildParentMap(root);
 
    // Find the nodes with values n1 and n2
    Node p = null, q = null;
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
      Node node = queue.poll();
      if (node.data == n1) {
        p = node;
      }
      if (node.data == n2) {
        q = node;
      }
      if (node.left != null) {
        queue.add(node.left);
      }
      if (node.right != null) {
        queue.add(node.right);
      }
    }
 
    // Add all the ancestors of the first node to a set
    // or a list
    Set<Node> ancestors = new HashSet<>();
    while (p != null) {
      ancestors.add(p);
      p = parentMap.get(p);
    }
 
    // Traverse up from the second node and check if
    // each ancestor is already in the set or the list
    while (q != null) {
      if (ancestors.contains(q)) {
        return q.data;
      }
      q = parentMap.get(q);
    }
 
    return -1; // No common ancestor found
  }
 
  public static void main(String[] args)
  {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
 
    System.out.println("LCA(4, 5) = "
                       + findLCA(root, 4, 5));
    System.out.println("LCA(4, 6) = "
                       + findLCA(root, 4, 6));
    System.out.println("LCA(3, 4) = "
                       + findLCA(root, 3, 4));
    System.out.println("LCA(3, 4) = "
                       + findLCA(root, 2, 4));
  }
}

Python3

from collections import deque
 
# Definition of a binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function to build a hash table or a map of parent
# pointers for each node in the tree
def buildParentMap(root):
    parentMap = {}
    parentMap[root] = None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node.left:
            parentMap[node.left] = node
            queue.append(node.left)
        if node.right:
            parentMap[node.right] = node
            queue.append(node.right)
    return parentMap
 
# Function to find the lowest common ancestor of two nodes
# using an auxiliary data structure
def findLCA(root, n1, n2):
    # Build a hash table or a map of parent pointers for
    # each node in the tree
    parentMap = buildParentMap(root)
 
    # Find the nodes with values n1 and n2
    p, q = None, None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node.data == n1:
            p = node
        if node.data == n2:
            q = node
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
 
    # Add all the ancestors of the first node to a set or a
    # list
    ancestors = set()
    while p:
        ancestors.add(p)
        p = parentMap[p]
 
    # Traverse up from the second node and check if each
    # ancestor is already in the set or the list
    while q:
        if q in ancestors:
            return q.data
        q = parentMap[q]
 
    return -1 # No common ancestor found
 
# Driver code
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
 
    print("LCA(4, 5) = ", findLCA(root, 4, 5))
    print("LCA(4, 6) = ", findLCA(root, 4, 6))
    print("LCA(3, 4) = ", findLCA(root, 3, 4))
    print("LCA(2, 4) = ", findLCA(root, 2, 4))

C#

using System;
using System.Collections.Generic;
 
// Definition of a binary tree node
class Node
{
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class MainClass
{
    // Function to build a hash table or a map of parent
    // pointers for each node in the tree
    static Dictionary<Node, Node> BuildParentMap(Node root)
    {
        Dictionary<Node, Node> parentMap = new Dictionary<Node, Node>();
        parentMap.Add(root, null);
        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(root);
        while (queue.Count != 0)
        {
            Node node = queue.Dequeue();
            if (node.left != null)
            {
                parentMap.Add(node.left, node);
                queue.Enqueue(node.left);
            }
            if (node.right != null)
            {
                parentMap.Add(node.right, node);
                queue.Enqueue(node.right);
            }
        }
        return parentMap;
    }
 
    // Function to find the lowest common ancestor of two
    // nodes using an auxiliary data structure
    static int FindLCA(Node root, int n1, int n2)
    {
        // Build a hash table or a map of parent pointers
        // for each node in the tree
        Dictionary<Node, Node> parentMap = BuildParentMap(root);
 
        // Find the nodes with values n1 and n2
        Node p = null, q = null;
        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(root);
        while (queue.Count != 0)
        {
            Node node = queue.Dequeue();
            if (node.data == n1)
            {
                p = node;
            }
            if (node.data == n2)
            {
                q = node;
            }
            if (node.left != null)
            {
                queue.Enqueue(node.left);
            }
            if (node.right != null)
            {
                queue.Enqueue(node.right);
            }
        }
 
        // Add all the ancestors of the first node to a set
        // or a list
        HashSet<Node> ancestors = new HashSet<Node>();
        while (p != null)
        {
            ancestors.Add(p);
            p = parentMap[p];
        }
 
        // Traverse up from the second node and check if
        // each ancestor is already in the set or the list
        while (q != null)
        {
            if (ancestors.Contains(q))
            {
                return q.data;
            }
            q = parentMap[q];
        }
 
        return -1; // No common ancestor found
    }
 
    public static void Main()
    {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
 
        Console.WriteLine("LCA(4, 5) = " + FindLCA(root, 4, 5));
        Console.WriteLine("LCA(4, 6) = " + FindLCA(root, 4, 6));
        Console.WriteLine("LCA(3, 4) = " + FindLCA(root, 3, 4));
        Console.WriteLine("LCA(2, 4) = " + FindLCA(root, 2, 4));
    }
}
 
// This code is contributed by akashish__

Javascript

// javascript code addition 
 
// Definition of a binary tree node
class Node {
  constructor(item) {
    this.data = item;
    this.left = null;
    this.right = null;
  }
}
 
// Function to build a hash table or a map of parent
// pointers for each node in the tree
function buildParentMap(root) {
  const parentMap = new Map();
  parentMap.set(root, null);
  const queue = [];
  queue.push(root);
  while (queue.length > 0) {
    const node = queue.shift();
    if (node.left != null) {
      parentMap.set(node.left, node);
      queue.push(node.left);
    }
    if (node.right != null) {
      parentMap.set(node.right, node);
      queue.push(node.right);
    }
  }
  return parentMap;
}
 
// Function to find the lowest common ancestor of two
// nodes using an auxiliary data structure
function findLCA(root, n1, n2) {
  // Build a hash table or a map of parent pointers
  // for each node in the tree
  const parentMap = buildParentMap(root);
 
  // Find the nodes with values n1 and n2
  let p = null, q = null;
  const queue = [];
  queue.push(root);
  while (queue.length > 0) {
    const node = queue.shift();
    if (node.data === n1) {
      p = node;
    }
    if (node.data === n2) {
      q = node;
    }
    if (node.left != null) {
      queue.push(node.left);
    }
    if (node.right != null) {
      queue.push(node.right);
    }
  }
 
  // Add all the ancestors of the first node to a set
  // or a list
  const ancestors = new Set();
  while (p != null) {
    ancestors.add(p);
    p = parentMap.get(p);
  }
 
  // Traverse up from the second node and check if
  // each ancestor is already in the set or the list
  while (q != null) {
    if (ancestors.has(q)) {
      return q.data;
    }
    q = parentMap.get(q);
  }
 
  return -1; // No common ancestor found
}
 
// Test the function
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
 
console.log("LCA(4, 5) = " + findLCA(root, 4, 5));
console.log("LCA(4, 6) = " + findLCA(root, 4, 6));
console.log("LCA(3, 4) = " + findLCA(root, 3, 4));
console.log("LCA(2, 4) = " + findLCA(root, 2, 4));
 
// The code is contributed by Nidhi goel.

Output

LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3,4) = 1
LCA(2, 4) = 2

Time Complexity: O(n),

The time complexity of the given code is O(n), where n is the number of nodes in the binary tree.

Building the parent map for each node in the tree requires visiting each node once, which takes O(n) time. Finding the nodes with values n1 and n2 requires visiting each node once, which also takes O(n) time. Traversing up from the second node and checking if each ancestor is already in the set or the list takes O(h) time, where h is the height of the binary tree.

In the worst case, the height of the binary tree is O(n), if the binary tree is skewed. Therefore, the overall time complexity of the given code is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n),

The space complexity of the given code is O(n) in the worst case. This is because the size of the parent map built for each node in the tree is O(n). Additionally, the set of ancestors can also contain all the nodes in the binary tree in the worst case, which also takes O(n) space. Finally, the queue used for traversing the binary tree takes O(n) space. Therefore, the overall space complexity of the given code is O(n) + O(n) + O(n) = O(n).

We have discussed an efficient solution to find LCA in Binary Search Tree. In Binary Search Tree, using BST properties, we can find LCA in O(h) time where h is the height of the tree. Such an implementation is not possible in Binary Tree as keys Binary Tree nodes don’t follow any order.

You may like to see the below articles as well :
LCA using Parent Pointer
Lowest Common Ancestor in a Binary Search Tree.
Find LCA in Binary Tree using RMQ

GeeksforGeeks

Improve

Previous Article

Maximum sum of nodes in Binary tree such that no two are adjacent

Height of a generic tree from parent array

Similar Reads

Lowest Common Ancestor in a Binary Tree | Set 3 (Using RMQ)

Given a rooted tree, and two nodes are in the tree, find the Lowest common ancestor of both the nodes. The LCA for two nodes u and v is defined as the farthest node from the root that is the ancestor to both u and v. Prerequisites: LCA | SET 1 Example for the above figure : Input : 4 5 Output : 2 Input : 4 7 Output : 1 Converting LCA to RMQ(Range M

Lowest Common Ancestor of the deepest leaves of a Binary Tree

Given a Binary Tree consisting of N nodes having distinct values from the range [1, N], the task is to find the lowest common ancestor of the deepest leaves of the binary tree. Examples: Input: Output: 1Explanation: The deepest leaf nodes of the tree are {8, 9, 10}. Lowest common ancestor of these nodes is 1. Input: Output: 6 Approach: The given pr

Lowest Common Ancestor in a Binary Tree using Parent Pointer

Given values of two nodes in a Binary Tree, find the Lowest Common Ancestor (LCA). It may be assumed that both nodes exist in the tree. For example, consider the Binary Tree in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8. Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T t

Lowest Common Ancestor in a Binary Search Tree.

Given two values n1 and n2 in a Binary Search Tree, find the Lowest Common Ancestor (LCA). You may assume that both values exist in the tree. Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

Lowest Common Ancestor for a Set of Nodes in a Rooted Tree

Given a rooted tree with N nodes, the task is to find the Lowest Common Ancestor for a given set of nodes V of that tree. Examples: Input: 1 / | \ 2 3 4 / \ | | 5 6 7 10 / \ 8 9 V[] = {7, 3, 8, 9} Output: 3 Input: 1 / | \ 2 3 4 / \ | | 5 6 7 10 / \ 8 9 V[] = {4, 6, 7} Output: 1 Approach: We can observe that the Lowest Common Ancestors for any set o

Lowest Common Ancestor in Parent Array Representation

Given a binary tree represented as parent array, find Lowest Common Ancestor between two nodes 'm' and 'n'. In the above diagram, LCA of 10 and 14 is 12 and LCA of 10 and 12 is 12. Make a parent array and store the parent of ith node in it. Parent of root node should be -1. Now, access all the nodes from the desired node 'm' till root node and mark

Least Common Ancestor of any number of nodes in Binary Tree

Given a binary tree (not a binary search tree) and any number of Key Nodes, the task is to find the least common ancestor of all the key Nodes. Following is the definition of LCA from Wikipedia: Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (w

Find path between lowest and highest value in a Binary tree

Given a binary tree consisting of N nodes. Find the path between the node having the lowest value to the node having the highest value. There is no restriction on the traversal, i.e. the tree can be traversed upward, bottom, left and right. Examples: Input: N = 8 2 / \ 1 6 / \ \ 4 21 26 / \5 7 {(2), (1, 6), (4, 21), (26), (5), (7)}Output: 1 -> 2

Tarjan's off-line lowest common ancestors algorithm

Prerequisite : LCA basics, Disjoint Set Union by Rank and Path CompressionWe are given a tree(can be extended to a DAG) and we have many queries of form LCA(u, v), i.e., find LCA of nodes ‘u’ and ‘v’.We can perform those queries in O(N + QlogN) time using RMQ, where O(N) time for pre-processing and O(log N) for answering the queries, where N = numb

K-th ancestor of a node in Binary Tree | Set 3

Given a binary tree in which nodes are numbered from 1 to N. Given a node and a positive integer K. We have to print the Kth ancestor of the given node in the binary tree. If there does not exist any such ancestor then print -1.For example in the below given binary tree, 2nd ancestor of node 4 and 5 is 1. 3rd ancestor of node 4 will be -1. Approach

Article Tags :

Practice Tags :