Lowest Common Ancestor of a Binary Tree 

In computer science, a binary tree is a widely used structure for organizing data hierarchically. The lowest common ancestor of a binary tree is a fundamental idea that finds the lowest common ancestor of two specified nodes (or several nodes). It is often used to solve problems that involve trees, networks, and relationships. In this blog, let us explore the lowest common ancestor of a binary tree with examples in detail.

Table of Contents:

• What is Lowest Common Ancestor (LCA) in a Binary Tree?
• Problem Statement and Example
• Methods to Find Lowest Common Ancestor (LCA) in a Binary Tree
  • Approach 1: Using Root-to-Node Paths
  • Approach 2: Using Single Traversal (Recursive Method)
  • Approach 3: Using Parent Pointers and Depth Calculation
• Applications of Lowest Common Ancestor
• Common Mistakes and Optimization Tips
• Best Practices for LCA Implementation
• Conclusion

What is Lowest Common Ancestor (LCA) in a Binary Tree?

In data structures, a binary tree is a common way to organize data in a tree form. Each node in a binary tree has at most two children, which we call the left child and the right child. Many of the problems based on tree structure depend on finding relations between nodes, and an important concept that often comes up is the lowest common ancestor of a binary tree.

The lowest common ancestor (LCA) of two nodes in a binary tree is the lowest or deepest node that has both nodes as descendants. It is the common parent of both nodes and the farthest from the root.

Example:

• If we want to find the lowest common ancestor of 4 and 5, the answer will be 2, as node 2 is the parent of both 4 and 5.
• If we want to find the lowest common ancestor of 4 and 3, the answer will be 1, as node 1 is the root and both 4 and 3 come under it.

So, the lowest common ancestor of a binary tree is used to help us find out the relationship between the two given nodes.

Unlock Python: Power Up Your Programming Skills!

Dive into real-world coding projects and become confident in writing clean, efficient Python code

Explore Program

Problem Statement and Example

Suppose you have a binary tree and two specific values to v1 and v2. Your task will be to find the Lowest Common Ancestor (LCA) of the nodes that have the values v1 and v2. The Lowest Common Ancestor of two nodes (e.g., node1 and node2) in a binary tree is the lowest node that has both node1 and node2 as descendants.

(Note: A node can be a descendant of itself.)

Example: The given picture below is the binary tree:

With the help of the above binary tree, find out:

• LCA(4, 5)
• LCA(7, 4)
• LCA(5, 8)

Output:

Explanation:

• Node 2 is the lowest node having both 4 and 5 as descendants.
• Node 4 is the lowest node that includes both 7 and 4.
• Node 1 is the lowest node containing 5 and 8.

Methods to Find Lowest Common Ancestor (LCA) in a Binary Tree

Let us explore different approaches that we can use to find the lowest common ancestor of a binary tree.

Approach 1: Using Root-to-Node Paths

Each binary tree has a distinct path from the root to each node. Therefore, there will be a path from the root to n1 and from the root to n2. The two paths will have some common nodes. The last node that is found in both of the paths is called the lowest common ancestor (LCA).

Algorithm Steps

1. Find and store the path from the root to node n1 in a list and name it path1.
2. Similarly, find and store the path that originates from the root to node n2 in a list and name it path2.
3. Traverse through both lists and compare until you find a mismatch in node values.
4. The node that had a matching value between the two lists, previous to the mismatch, is the LCA.

Java Implementation

import java.util.*;

public class Main {

    // Node class
    static class Node {
        int val;
        Node left, right;

        Node(int val) {
            this.val = val;
        }
    }

    // Lists to store the path
    static List<Integer> path1;
    static List<Integer> path2;

    // Function to find the path from the root node to the target node
    static boolean findPath(Node root, int val, List<Integer> path) {
        // Return false if we encounter a null node
        if (root == null)
            return false;

        path.add(root.val);

        // Return true if we encounter the target node
        if (root.val == val)
            return true;

        // Return true if we find the target node in any of the subtrees
        if (findPath(root.left, val, path) || findPath(root.right, val, path))
            return true;

        // Backtrack by removing the last element of the path list
        path.remove(path.size() - 1);

        // Return false if the target node is not found
        return false;
    }

    // Helper function to find the LCA
    static int findLCA(Node root, int n1, int n2) {
        // Using a function to find the path from root to n1 or n2
        if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
            System.out.println("Please enter valid input");
            return -1;
        }

        int ind;
        // Now iterate over the path lists found
        for (ind = 0; ind < path1.size() && ind < path2.size(); ind++) {
            // If there is a mismatch, break the loop
            if (!path1.get(ind).equals(path2.get(ind)))
                break;
        }

        // Return the node encountered just before the mismatch
        return path1.get(ind - 1);
    }

    // Function to find the LCA
    static int LCA(Node root, int n1, int n2) {
        path1 = new ArrayList<>();
        path2 = new ArrayList<>();
        return findLCA(root, n1, n2);
    }

    public static void main(String[] args) {
        // Making the following tree
        //          1
        //        /   \
        //       2     3
        //      / \     \
        //     4   5     6
        //      \       / \
        //       7     8   9

        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);

        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));
        // Passing wrong input
        System.out.println("LCA of 5 and 10 is " + LCA(root, 5, 10));
    }
}

Output:

Explanation: In this case, the Lowest Common Ancestor of two nodes in a binary tree is calculated using the following Java code, and it is calculated by storing the path to the node starting at the root.

Python Implementation

# Node class
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None    

# Lists to store the path
path1 = []
path2 = []

# Function to find the path from the root node to the target node
def findPath(root, val, path):
    # Return false if we encounter a None node
    if root is None:
        return False

    path.append(root.val)

    # Return true if we encounter the target node
    if root.val == val:
        return True

    # Return true if we find the target node in any of the subtrees
    if findPath(root.left, val, path) or findPath(root.right, val, path):
        return True

    # Backtrack by removing the last element from the path list
    path.pop()

    # Return false if nothing worked out
    return False

# Helper function to find the LCA
def findLCA(root, n1, n2):
    # Using a function to find the path from root to n1 or n2
    if not findPath(root, n1, path1) or not findPath(root, n2, path2):
        print("Please enter valid input")
        return -1

    ind = 0
    # Now iterate over the path lists found
    while ind < len(path1) and ind < len(path2):
        # If there is a mismatch, break the loop
        if path1[ind] != path2[ind]:
            break
        ind += 1

    # Return the node encountered just before the mismatch
    return path1[ind - 1]

# Function to find the LCA
def LCA(root, n1, n2):
    global path1, path2
    path1 = []
    path2 = []
    return findLCA(root, n1, n2)

# Driver code
# Making the following tree
#          1
#        /   \
#       2     3
#      / \     \
#     4   5     6
#      \       / \
#       7     8   9

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))
# Passing wrong input
print("LCA of 5 and 10 is", LCA(root, 5, 10))

Output:

Explanation: In this case, we are going to use this Python code to compute the Lowest Common Ancestor of two nodes in a binary tree.

Complexity Analysis

• Time Complexity: Traversal down a path is O(n), where n is the number of nodes, so the total is O(n).
• Space Complexity: In the worst case (deepest leaf), path list size = O(h) and recursion depth = O(h)  =>O(h) overall, where h = height of the binary tree.

Approach 2: Using Single Traversal (Recursive Method)

The single traversal recursive technique is an optimal way to find the lowest common ancestor of a binary tree in just a single pass.

Instead of determining the individual paths for each one of the nodes, like the first approach, this technique performs a recursive search of the tree only once and identifies the lowest common ancestor of a binary tree.

Algorithm Steps

1. Use two boolean flags, b1 and b2, to check whether both target nodes exist in the tree.

2. Define a recursive helper findLCA(node, n1, n2):

• If node == null, return null.
• If node.val == n1, set b1 = true and return node.
• If node.val == n2, set b2 = true and return node.
• Recursively call for left and right subtrees.
• If both left and right results are non-null, the current node is the LCA.
• Return whichever subtree gives a non-null result.
  

3. If both b1 and b2 are true, return LCA value; otherwise, print “Invalid input”.

Java Implementation

import java.util.*;

public class Main {

    // Node class
    static class Node {
        int val;
        Node left, right;

        Node(int val) {
            this.val = val;
        }
    }

    // Boolean variables to check if the target nodes exist in the tree
    static boolean b1, b2;

    // Helper function to find the LCA
    static Node findLCA(Node node, int n1, int n2) {
        // Base case
        if (node == null)
            return null;

        // Declare a variable to store the answer
        Node ans = null;

        // If the node's value matches n1
        if (node.val == n1) {
            b1 = true;
            ans = node;
        } 
        // If the node's value matches n2
        else if (node.val == n2) {
            b2 = true;
            ans = node;
        }

        // Check for the target nodes in left and right subtrees
        Node leftAns = findLCA(node.left, n1, n2);
        Node rightAns = findLCA(node.right, n1, n2);

        // If current node matches one of the targets
        if (ans != null)
            return ans;

        // If targets are found in left and right subtrees
        if (leftAns != null && rightAns != null)
            return node;

        // Otherwise, return the non-null subtree answer
        return leftAns != null ? leftAns : rightAns;
    }

    // Function to find the LCA
    static int LCA(Node root, int n1, int n2) {
        // Initialize b1 and b2
        b1 = false;
        b2 = false;

        // Find potential LCA
        Node lca = findLCA(root, n1, n2);

        // If both nodes exist in the tree
        if (b1 && b2) {
            return lca.val;
        }

        System.out.println("Please enter valid input");
        return -1;
    }

    public static void main(String[] args) {
        // Making the following tree
        //          1
        //        /   \
        //       2     3
        //      / \     \
        //     4   5     6
        //      \       / \
        //       7     8   9

        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);

        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));
        // Passing wrong input
        System.out.println("LCA of 5 and 10 is " + LCA(root, 5, 10));
    }
}

Output:

Explanation: In this case, this code in Java is applied to determine the lowest common ancestor of two nodes in a binary tree with a single journey and U-B check flags to determine whether the two nodes exist.

Python Implementation

# Node class
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None    

# Boolean variables to check if target nodes exist in the tree
boolean = [False, False]

# Helper function to find the LCA
def findLCA(node, n1, n2):
    # Base case
    if node is None:
        return None

    # Variable to store the answer
    ans = None

    # If the node's value matches n1
    if node.val == n1:
        boolean[0] = True
        ans = node
    # If the node's value matches n2
    elif node.val == n2:
        boolean[1] = True
        ans = node

    # Check for the target nodes in left and right subtrees
    leftAns = findLCA(node.left, n1, n2)
    rightAns = findLCA(node.right, n1, n2)

    # If current node matches one of the targets
    if ans is not None:
        return ans

    # If targets are found in left and right subtrees
    if leftAns is not None and rightAns is not None:
        return node

    # Otherwise, return the non-null subtree answer
    return leftAns if leftAns is not None else rightAns

# Function to find the LCA
def LCA(root, n1, n2):
    global boolean
    boolean = [False, False]  # Initialize boolean list

    # Find potential LCA
    lca = findLCA(root, n1, n2)

    # If both nodes exist in the tree
    if boolean[0] and boolean[1]:
        return lca.val

    print("Please enter valid input")
    return -1

# Driver code
# Making the following tree
#          1
#        /   \
#       2     3
#      / \     \
#     4   5     6
#      \       / \
#       7     8   9

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))
# Passing wrong input
print("LCA of 5 and 10 is", LCA(root, 5, 10))

Output:

Explanation: In this case, the Lowest Common Ancestor (LCA) of two nodes in a binary tree is computed in a single traversal by Python code using a set of flags that are used to ensure that both nodes are present.

Complexity Analysis:

• Time Complexity: O(n)
  (Every node is visited only once.)
• Space Complexity: O(h)
  (The recursive call stack can go up to the height of the tree.)

Approach 3: Using Parent Pointers and Depth Calculation

In previous techniques, we have utilized recursive traversals and path storage to find the lowest common ancestor of a binary tree. However, both of these approaches required traversing the tree multiple times. This third approach is designed for efficiency. By using parent references and comparing depths, LCA can be found in linear time with very limited recursion time

Algorithm Steps

1. Store Parents and Levels:
   • Use a queue to perform a level-order traversal (BFS).
   • For each node visited, store its parent and its level (distance from the root).
     
2. Equalize the Depth:
   • Compare the depth of both target nodes.
   • Move the deeper node upward until both are at the same level.
     
3. Find the LCA:
   • Move both nodes one step at a time (toward their parents).
   • The first node where both meet is the LCA.
     
4. Return Result:
   • If either of the nodes doesn’t exist in the tree, return -1.

Java Implementation

import java.util.*;

public class Main {

// Node structure
static class Node {
    int val;
    Node left, right;

    Node(int val) {
        this.val = val;
    }
}

// Function to find LCA using parent map and depth map
static int LCA(Node root, int n1, int n2) {
    if (root == null) return -1;

    Map<Node, Node> parent = new HashMap<>();
    Map<Node, Integer> depth = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();

    parent.put(root, null);
    depth.put(root, 0);
    queue.add(root);

    Node node1 = null, node2 = null;

    // BFS to store parent and depth
    while (!queue.isEmpty()) {
        Node current = queue.poll();

        if (current.val == n1) node1 = current;
        if (current.val == n2) node2 = current;

        if (current.left != null) {
            parent.put(current.left, current);
            depth.put(current.left, depth.get(current) + 1);
            queue.add(current.left);
        }

        if (current.right != null) {
            parent.put(current.right, current);
            depth.put(current.right, depth.get(current) + 1);
            queue.add(current.right);
        }
    }

    // If either node doesn’t exist
    if (node1 == null || node2 == null)
        return -1;

    // Equalize depth
    while (depth.get(node1) > depth.get(node2))
        node1 = parent.get(node1);

    while (depth.get(node2) > depth.get(node1))
        node2 = parent.get(node2);

    // Move up together until both nodes match
    while (node1 != node2) {
        node1 = parent.get(node1);
        node2 = parent.get(node2);
    }

    return node1.val;
}

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.right = new Node(6);
    root.left.left.right = new Node(7);
    root.right.right.right = new Node(8);

    System.out.println("LCA of 7 and 5: " + LCA(root, 7, 5));
    System.out.println("LCA of 8 and 3: " + LCA(root, 8, 3));
    System.out.println("LCA of 7 and 8: " + LCA(root, 7, 8));
}

}

Output:

Explanation: Here, this Java code finds the lowest common ancestor of two nodes in a binary tree using BFS to build parent and depth maps, then equalizes depth and traces ancestors upward.

Python Implementation

# Node class
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None    

# Function to find the LCA using parent pointers
def LCA(root, n1, n2):
    # Dictionary to keep track of parents
    parent = {}
    # Queue for BFS traversal
    q = []
    # Parent of the root is None
    parent[root] = None
    q.append(root)

    # Variables to store references to nodes with values n1 and n2
    x, y = None, None

    # BFS until both target nodes are found
    while q and (x is None or y is None):
        node = q.pop(0)  # dequeue

        if node.val == n1:
            x = node
        elif node.val == n2:
            y = node

        if node.left:
            parent[node.left] = node
            q.append(node.left)
        if node.right:
            parent[node.right] = node
            q.append(node.right)

    # If either node doesn't exist, LCA doesn't exist
    if x is None or y is None:
        return -1

    # Set to store the path from x to root
    ancestors = set()
    while x:
        ancestors.add(x)
        x = parent[x]

    # Move y up until we find a common ancestor
    while y not in ancestors:
        y = parent[y]

    return y.val

# Driver code
# Constructing the tree
#          1
#        /   \
#       2     3
#      / \     \
#     4   5     6
#      \       / \
#       7     8   9

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))
# Passing wrong input
print("LCA of 5 and 10 is", LCA(root, 5, 10))

Output:

Explanation: Here, this Python code finds the lowest common ancestor of two nodes in a binary tree using BFS to track parent pointers and then tracing ancestors to find the first common node.

Note: Using custom objects as dictionary keys in Python requires overriding __hash__ and __eq__. Without this, the BFS code may give errors.

Complexity Analysis

• Time Complexity: In the worst case, we need to traverse the entire tree, resulting in a time complexity of O(n) to find the LCA of a binary tree. Therefore, the overall time complexity becomes O(n). 
• Space Complexity: When traversing a binary tree using a level order approach, the maximum size of the queue may be O(n). Thus, the overall space complexity will be O(n).

Applications of Lowest Common Ancestor

The concept of LCA is fundamental and has many practical applications. Below are some common use cases for LCA.

1. Family Trees and Genealogy

In a family tree, LCA indicates the nearest common ancestor for two people. If you want to find the nearest common ancestor of two cousins, the LCA would be their shared grandparent.

2. File Systems and Folder Structures

Modern file systems like Windows or Linux use a tree structure to store folders and files. Finding the least common ancestor of two files is used to find their common parent folder. This would be used for actions like merging, backup synchronization, and permission checking.

Common Mistakes and Optimization Tips

1. Failing to Check the Existence of the Nodes: It is common for beginners to forget to check whether both of the nodes they are checking exist in the binary tree. Not checking for both nodes can lead to incorrect answers or errors, so keep in mind to verify that both target nodes exist before finding the lowest common ancestor of a binary tree.
2. Not Specifying the Base Case for Recursion: When applying recursion, sometimes learners neglect to specify the base case for recursion. Always make sure to return null whenever the current node is null to revert the recursion.
3. Confusing the Left and Right Subtree Results: Sometimes, students return the incorrect result when validating the left and right subtrees. If both left and right results are not null, then the current node to which the recursion is traversing is the lowest common ancestor of a binary tree.
4. Using Multiple Traversals: Searching for the path for both nodes using separate traversals slows you down. Use a single traversal to directly find the lowest common ancestor of a binary tree.

Best Practices for LCA Implementation

1. Check for Node Existence: Always check for the existence of both target nodes in the tree. If one node or both nodes do not exist, your algorithm should return a clear message or a null value.
2. Validate Edge Cases: Ensure that your code validates the edge case when both nodes are the same or when one node is the ancestor of another.
3.  Keep it Simple and Readable: Avoid unnecessary variables or a complicated logic flow. Use meaningful names for functions and short, clear comments for key steps.
4. Use Space Efficiently: Try to avoid using extra memory when not necessary. For example, if your recursive approach has already shown you the value, then do not store the full path.

Start Coding in Python for Free: No Experience Needed!

Begin writing actual Python code through interactive, beginner-friendly modules completely for free.

Explore Program

Conclusion

The lowest common ancestor of a binary tree is an important and useful concept that simplifies many problems related to tree data structures. If you read about different methods and best practices, you can find yourself implementing the LCA logic into real-world scenarios, like file systems and family trees. The stronger your understanding becomes, the better you will be at both programming and problem-solving, making it an essential topic for all programmers to understand.

Take your skills to the next level by enrolling in the Python Course today and gaining hands-on experience. Also, prepare for job interviews with Python Interview Questions prepared by industry experts.

Lowest Common Ancestor of a Binary Tree – FAQs