Vultr DocsLatest Content

Lowest Common Ancestor of a Binary Tree

Updated on 09 June, 2025
Lowest Common Ancestor of a Binary Tree header image

Problem Statement

In the given task, we are to determine the lowest common ancestor (LCA) of two specific nodes within a binary tree. The LCA between two nodes p and q is the deepest (or lowest) node that acts as an ancestral node to both p and q, inclusive of cases where a node can be its own ancestor. This task employs the classical understanding of ancestry within a tree structure, where the objective is to locate a node that directly connects the chosen nodes either through direct lineage or through common descent.

Examples

Example 1

Input:

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output:

3

Explanation:

The LCA of nodes 5 and 1 is 3.

Example 2

Input:

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output:

5

Explanation:

The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3

Input:

root = [1,2], p = 1, q = 2

Output:

1

Constraints

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

Approach and Intuition

The Lowest Common Ancestor (LCA) problem is a well-established problem in computer science, particularly within data structures concerning trees and graphs. To decode the LCA, one can leverage several intuitive observations from example evaluations:

Example 1

  • Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
  • Output: 3
  • Explanation: The node values 5 and 1 are descended from node 3. Hence, node 3 is their lowest common ancestor.

Example 2

  • Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
  • Output: 5
  • Explanation: Here, node 4 directly descends from node 5, and since a node can be its own ancestor, the LCA of nodes 5 and 4 is node 5.

Example 3

  • Input: root = [1,2], p = 1, q = 2
  • Output: 1
  • Explanation: The node 2 is a direct descendant of node 1. Given that a node can be a descendant of itself, node 1 is the LCA of nodes 1 and 2.

From these observations, the approach to finding the LCA can be described as follows:

  1. Start from the root and traverse the tree.
  2. If you encounter either p or q during the traversal, that node itself becomes a potential LCA candidate.
  3. If traversal leads to locating both p and q on different subtrees of the current node, then the current node is the LCA.
  4. If both nodes lie in the same subtree, move the search to that subtree and continue.

The logic primarily revolves around efficient tree traversal and keeping track of the paths or lineage of the nodes in question. Depth-first search (DFS) is particularly effective here, allowing the recursive exploration of all potential paths within the tree, while backtracking ensures that once a node has been evaluated, its ancestors are considered for LCA candidacy. This process continues until the conditions for determining the LCA, as illustrated through the examples, are conclusively met.

Solutions

  • Java
  • Python
java 
class Solution {
    // Constants to represent the state of node traversal
    private static int PENDING_BOTH_CHILDREN = 2;
    private static int DONE_LEFT_CHILD = 1;
    private static int COMPLETED_TRAVERSAL = 0;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<Pair<TreeNode, Integer>> traversalStack = new Stack<>();

        // Begin with the root node, having both children pending
        traversalStack.push(new Pair<TreeNode, Integer>(root, PENDING_BOTH_CHILDREN));

        // Flag to identify whether one of the target nodes has been found
        boolean isOneNodeFound = false;

        // Variable to hold the lowest common ancestor
        TreeNode ancestor = null;

        // Node to help with child node processing
        TreeNode nextNode = null;

        while (!traversalStack.isEmpty()) {
            Pair<TreeNode, Integer> nodePair = traversalStack.peek();
            TreeNode currentNode = nodePair.getKey();
            int state = nodePair.getValue();

            if (state != COMPLETED_TRAVERSAL) {
                if (state == PENDING_BOTH_CHILDREN) {
                    if (currentNode == p || currentNode == q) {
                        if (isOneNodeFound) {
                            return ancestor;
                        } else {
                            isOneNodeFound = true;
                            ancestor = traversalStack.peek().getKey();
                        }
                    }
                    nextNode = currentNode.left;
                } else {
                    nextNode = currentNode.right;
                }
                traversalStack.pop();
                traversalStack.push(new Pair<TreeNode, Integer>(currentNode, state - 1));
                if (nextNode != null) {
                    traversalStack.push(new Pair<TreeNode, Integer>(nextNode, PENDING_BOTH_CHILDREN));
                }
            } else {
                if (ancestor == traversalStack.pop().getKey() && isOneNodeFound) {
                    ancestor = traversalStack.peek().getKey();
                }
            }
        }

        return null;
    }
}

The Java solution provided implements a method to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree using an iterative depth-first search (DFS) approach. Here's a summary of the code functionality and structure:

  • The solution uses a stack to manage the DFS traversal state of each node, utilizing pairs of a tree node and an integer state. The integer state represents the traversal progress for the node's children.
  • A Pair object holds each node and its traversal state. Three states manage the traversal progress:
    • PENDING_BOTH_CHILDREN - both children of the node still need to be processed.
    • DONE_LEFT_CHILD - only the left child has been processed.
    • COMPLETED_TRAVERSAL - both children have been processed.
  • The algorithm starts by pushing the root node with the PENDING_BOTH_CHILDREN state onto the stack.
  • The isOneNodeFound flag is used to indicate if one of the target nodes is found during the traversal. The ancestor variable holds the last common ancestor encountered during the search.
  • The main loop processes each node according to its current state:
    • If in the PENDING_BOTH_CHILDREN state and the current node is one of the nodes (p or q), the code checks the isOneNodeFound flag. If the flag is already set, it returns the current ancestor. If not, it sets the flag and updates the ancestor.
    • The node's children are pushed onto the stack appropriately based on the traversal state.
    • If a node completes traversal (COMPLETED_TRAVERSAL), it updates the ancestor based on the stack's state.
  • The loop continues until the stack is empty. If both nodes are found, the ancestor is the LCA; otherwise, it returns null if the LCA does not exist within the given part of the tree.

This method effectively tracks back on the path taken and updates possible ancestors as nodes are completely processed, ensuring non-recursive tree traversal management with explicit state tracking.

python 
class AncestorFinder:

    # Different states for traversal steps
    UNVISITED = 2
    LEFT_VISITED = 1
    BOTH_VISITED = 0

    def findLCA(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Stack to keep track of the navigation of nodes
        traversal_stack = [(root, AncestorFinder.UNVISITED)]

        # Flag to mark the encounter of either p or q
        first_found = False

        # Index of Lowest Common Ancestor in stack
        LCA_index = -1

        # Continue until all nodes are processed
        while traversal_stack:

            # Current node and its state
            current_node, state = traversal_stack[-1]

            # Process unless both children are visited
            if state != AncestorFinder.BOTH_VISITED:
                
                # If this is first traversal to the node
                if state == AncestorFinder.UNVISITED:

                    # Check if the current_node is one of p or q
                    if current_node == p or current_node == q:

                        # If one is already found this means we have discovered both
                        if first_found:
                            return traversal_stack[LCA_index][0]
                        else:
                            # Mark the flag true, and note the current LCA index
                            first_found = True
                            LCA_index = len(traversal_stack) - 1

                    # First move to the left child
                    next_node = current_node.left
                else:
                    # Move to the right child
                    next_node = current_node.right

                # Mark this node as partially visited by decreasing the state
                traversal_stack.pop()
                traversal_stack.append((current_node, state - 1))

                # If we have a valid child node, push it to stack
                if next_node:
                    traversal_stack.append((next_node, AncestorFinder.UNVISITED))
            else:
                # If both children are visited, we can retract
                if first_found and LCA_index == len(traversal_stack) - 1:
                    LCA_index -= 1
                traversal_stack.pop()

        return None

This solution implements a method to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree using a manual stack for iterative traversal, which avoids recursion. Understand the Python implementation through these concise points:

  • It defines a class AncestorFinder with an embedded method findLCA, which takes the root of the tree and two nodes, p and q, as inputs.
  • The method utilizes three states (UNVISITED, LEFT_VISITED, BOTH_VISITED) to monitor the traversal status of each node during the process.
  • The core of the algorithm uses a stack, traversal_stack, to manage the state and node pairs as the tree is traversed.
  • Two flags, first_found and LCA_index, help in identifying when both the required nodes are found and in determining the position of the lowest common ancestor in the stack.
  • The logic in findLCA involves:
    • Pushing nodes onto the stack until a node is found that matches either p or q.
    • Marking the index of that node if it's the first of the two nodes discovered; if both are found, the LCA is determined from the stack based on the stored indices.
    • Adjusting the states and traversing to left and right children as determined by conditional checks.

In an iterative depth-first search manner, the algorithm ensures that it checks each node and its children, pushing and popping from the stack, until the LCA is identified or the stack is empty. If both nodes p and q are encountered during the traversal, the method returns the LCA; otherwise, it returns None. Ensure robust exception handling and boundary checks when applying this solution in different scenarios.

Comments

No comments yet.