236. Lowest Common Ancestor Of A Binary Tree

5 min read

Lowest Common Ancestor of a Binary Tree

The lowest common ancestor (LCA) of two nodes in a binary tree is the deepest node that has both nodes as descendants, where we consider a node to be its own descendant. Even so, this concept is fundamental in tree data structures and appears frequently in algorithm design, competitive programming, and real-world applications like file system navigation and network routing. Plus, understanding how to find the LCA efficiently is a valuable skill for any programmer working with hierarchical data. In this article, we will explore the definition, problem statement, multiple approaches to solve the LCA problem, and important considerations for implementation.

What Is the Lowest Common Ancestor?

The lowest common ancestor of two nodes in a binary tree is the deepest node that lies on the path between them. Here's one way to look at it: if we have nodes A and B in a binary tree, their LCA is the node where the paths from the root to A and from the root to B diverge. If we consider the tree as rooted, the LCA is the first node encountered when traveling upward from both nodes until we find a common parent. This node is the lowest (deepest) such common ancestor because any higher node would be an ancestor of both but not the lowest one Most people skip this — try not to..

Understanding the LCA is crucial because it helps solve various tree-related problems, such as finding the k-th ancestor of a node, determining the nearest common ancestor in a forest, and optimizing search operations in hierarchical databases. The classic problem involves being given the root of a binary tree and two distinct nodes, and we need to return the LCA of these two nodes Small thing, real impact. Which is the point..

Problem Statement

Given the root of a binary tree and two nodes (identified by their values), we need to find and return the lowest common ancestor of these two nodes. Practically speaking, the tree may not be balanced, and the nodes could be anywhere in the tree, including being direct children of the root. The solution must work efficiently even for large trees with thousands of nodes.

Let's consider a simple example to illustrate the concept. Suppose we have the following binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6

If we want to find the LCA of nodes 4 and 5, the answer is node 2, because node 2 is the deepest node that has both 4 and 5 as descendants. If we ask for the LCA of nodes 4 and 6, the answer is node 1, since node 1 is the root and the only common ancestor of these two nodes. The LCA of a node with itself is the node itself, as it is trivially the deepest common ancestor Practical, not theoretical..

Approach 1: Recursive Solution

The most straightforward way to find the LCA of two nodes in a binary tree is using a recursive depth-first search (DFS) approach. On top of that, the key insight is that if we can find one of the target nodes in the left subtree and the other in the right subtree, then the current node is the LCA. If both nodes are found in the same subtree (either left or right), then we continue the search in that subtree Worth keeping that in mind..

Most guides skip this. Don't.

Here's how the recursive algorithm works:

  1. If the current node is null, return null (base case).
  2. If the current node is one of the target nodes, return the current node.
  3. Recursively search for the left subtree.
  4. Recursively search for the right subtree.
  5. If both left and right recursive calls return non-null values, then the current node is the LCA (because we found one target in the left subtree and the other in the right).
  6. Otherwise, return whichever of the left or right recursive calls is non-null (or null if both are null).

This approach works because we are traversing the tree in a bottom-up manner, and we can immediately identify when we have found both nodes in different subtrees Which is the point..

Step-by-Step Algorithm

Let me break down the recursive approach into clear steps:

  • Step 1: Start at the root of the binary tree.
  • Step 2: Check if the current node is one of the two target nodes. If yes, return this node as a potential LCA.
  • Step 3: Recursively search the left subtree for the first target node.
  • Step 4: Recursively search the right subtree for the second target node.
  • Step 5: If both recursive calls return non-null values, then the current node is the LCA because it has one target in its left subtree and the other in its right subtree.
  • Step 6: If only one recursive call returns a non-null value, propagate that value up the recursion chain (since we've found one of the targets, and we need to continue searching in that direction).
  • Step 7: If both recursive calls return null, return null (meaning neither target was found in this subtree).

This algorithm has a time complexity of O(n) in the worst case, where n is the number of nodes in the tree, because we may need to visit every node once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack Most people skip this — try not to..

Approach 2: Iterative Solution Using Parent Pointers

Another common approach is to first find the paths from the root to each of the two target nodes, and then compare these paths to identify the LCA. This method involves two main steps:

  1. Finding the path to a node: We can use a simple DFS or BFS to trace the path from the root to a given target node, storing the nodes in a list.
  2. Finding the LCA: Once we have the paths to both nodes, we can compare them from the root downward. The last common node in both paths (excluding the root if it's not part of the common sequence) is the LCA.

Here's a more detailed breakdown:

  • Step 1: Create a helper function that finds the path from the root to a given target node. This function returns a list of nodes representing the path.
  • Step 2: Call this helper function twice—once for each target node—to get two paths.
  • Step 3: Traverse both paths simultaneously from the beginning. The last node where the paths match is the LCA.
  • **Step
Just Made It Online

Out Now

Connecting Reads

In the Same Vein

Thank you for reading about 236. Lowest Common Ancestor Of A Binary Tree. We hope the information has been useful. Feel free to contact us if you have any questions. See you next time — don't forget to bookmark!
⌂ Back to Home