Why does the recursive approach return the current node when both subtree results are non-null?

A non-null result from both sides means that the two targets have been found in different branches of the current node. Therefore, the current node is the deepest point where those branches meet.

Why is a single non-null result propagated upward?

If only one subtree returns a node, the useful information found so far lies entirely in that branch. Propagating it upward allows an ancestor to determine whether the other target appears in another branch.

Is the Lowest Common Ancestor necessarily the root?

No. The root is the LCA only when it is the deepest common ancestor of the two nodes. If both nodes lie inside the same subtree, their LCA can be much deeper.

Which approach is generally preferred?

The recursive DFS approach is usually preferred because the LCA is found in one traversal using O(H) auxiliary recursion space without storing complete paths or parent relationships.

Lowest Common Ancestor in a Binary Tree

Given the root of a binary tree and two nodes p and q present in the tree, find their Lowest Common Ancestor (LCA).

The LCA is the deepest node in the tree that is an ancestor of both p and q.

A node can also be considered an ancestor of itself. Therefore, if one of the given nodes lies on the path from the root to the other node, that node itself can be the LCA.

Example 1

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

Output:
3

Explanation:
Node 3 is the deepest node that is an ancestor of both nodes 5 and 1, so their Lowest Common Ancestor is 3.

Example 2

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

Output:
5

Explanation:
Node 5 is an ancestor of node 4. Since a node can be considered an ancestor of itself, the Lowest Common Ancestor is 5.

Practice it by yourself before moving onto the solutionTry now

Approach 1

Every node in a binary tree has exactly one path from the root.

Two lists, pathP and pathQ, are maintained. pathP stores the sequence of ancestors from the root to node p, while pathQ stores the corresponding sequence from the root to node q.

Once both paths are available, they remain identical from the root until their deepest common node. After that point, either the paths move into different branches or one of them ends.

Therefore, the last matching node in pathP and pathQ is the Lowest Common Ancestor.

This approach follows the definition directly, but two complete root-to-node paths must first be found and stored.

Algorithm

A path named pathP is constructed using DFS so that the complete ancestor chain from the root to node p is stored.
A second path named pathQ is constructed in the same way so that the ancestor chain from the root to node q is available.
Both paths are compared from their first position because their common prefix represents the nodes that are ancestors of both targets.
Matching nodes are processed until different nodes are encountered or one of the paths ends.
The last matching node is identified as the deepest node shared by both ancestor chains.
That node is returned as the Lowest Common Ancestor.

Dry Run

Lowest Common Ancestor Approach 1 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Stores the root-to-target path
  // using DFS and backtracking.
  bool findPath(
      TreeNode* node,
      TreeNode* target,
      vector<TreeNode*>& path
  ) {
      if (node == nullptr) {
          return false;
      }
28
      path.push_back(node);
30
      // The required ancestor chain is complete
      // once the target node is reached.
      if (node == target) {
          return true;
      }
36
      if (
          findPath(node->left, target, path) ||
          findPath(node->right, target, path)
      ) {
          return true;
      }
43
      // The node is removed when the target
      // is not present in this subtree.
      path.pop_back();
47
      return false;
  }
50
51public:
  // Finds the last common node in
  // the root-to-p and root-to-q paths.
  TreeNode* lowestCommonAncestor(
      TreeNode* root,
      TreeNode* p,
      TreeNode* q
  ) {
      vector<TreeNode*> pathP;
      vector<TreeNode*> pathQ;
61
      findPath(root, p, pathP);
      findPath(root, q, pathQ);
64
      TreeNode* lca = nullptr;
66
      int limit = min(
          pathP.size(),
          pathQ.size()
      );
71
      // Both paths share the same prefix
      // until their Lowest Common Ancestor.
      for (int i = 0; i < limit; i++) {
          if (pathP[i] != pathQ[i]) {
              break;
          }
78
          lca = pathP[i];
      }
81
      return lca;
  }
84};
85
86int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(5);
  root->right = new TreeNode(1);
  root->left->left = new TreeNode(6);
  root->left->right = new TreeNode(2);
  root->right->left = new TreeNode(0);
  root->right->right = new TreeNode(8);
  root->left->right->left = new TreeNode(7);
  root->left->right->right = new TreeNode(4);
96
  TreeNode* p = root->left;
  TreeNode* q = root->left->right->right;
99
  Solution solution;
101
  TreeNode* lca =
      solution.lowestCommonAncestor(root, p, q);
104
  cout << lca->val << endl;
106
  return 0;
108}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N). Each root-to-node search may visit up to N nodes, and performing two such searches still gives O(N) overall. Comparing pathP and pathQ requires at most O(H) additional time.

Space Complexity: O(H), where H is the height of the binary tree. The recursive call stack and the stored root-to-node paths can each contain at most H nodes. For a skewed tree, this can become O(N).

Approach 2

If every node knew its parent, the search could be performed upward instead of repeatedly moving downward from the root.

A mapping of:

node → parent

is first constructed.

A queue named nodesQueue is used for a level-order traversal because it stores the nodes whose children still need to be processed while the parent relationships are being built.

After the mapping has been constructed, an ancestors set is used to store every node encountered while moving from p toward the root. The set is chosen because it allows constant-time average membership checks when the ancestor chain of q is later examined.

Node q is then moved upward through its parent links. The first node encountered that already exists in ancestors is the deepest node shared by both ancestor chains and is therefore the LCA.

Algorithm

A parent mapping is constructed using a queue-based level-order traversal (BFS) so that every visited child is associated with its parent.
A queue named nodesQueue is maintained because it stores nodes whose children still need to be examined while the parent mapping is being created.
BFS is continued until parent information for both p and q has been discovered.
A set named ancestors is then created to store all nodes encountered while moving upward from p, allowing nodes in this ancestor chain to be checked efficiently.
Starting from p, parent links are repeatedly followed and every visited node is inserted into ancestors.
Starting from q, parent links are followed upward until a node already present in ancestors is encountered.
The first such node is returned because it is the lowest ancestor shared by both target nodes.

Dry Run

Lowest Common Ancestor Approach 2 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17public:
  // Builds parent relationships using BFS
  // and compares the ancestor chains.
  TreeNode* lowestCommonAncestor(
      TreeNode* root,
      TreeNode* p,
      TreeNode* q
  ) {
      unordered_map<TreeNode*, TreeNode*> parent;
26
      // nodesQueue stores nodes whose children
      // still need parent information.
      queue<TreeNode*> nodesQueue;
30
      parent[root] = nullptr;
      nodesQueue.push(root);
33
      // BFS continues until both target nodes
      // have known parent relationships.
      while (
          parent.find(p) == parent.end() ||
          parent.find(q) == parent.end()
      ) {
          TreeNode* node =
              nodesQueue.front();
42
          nodesQueue.pop();
44
          if (node->left != nullptr) {
              parent[node->left] = node;
              nodesQueue.push(node->left);
          }
49
          if (node->right != nullptr) {
              parent[node->right] = node;
              nodesQueue.push(node->right);
          }
      }
55
      // ancestors stores every node on
      // p's path from itself to the root.
      unordered_set<TreeNode*> ancestors;
59
      TreeNode* current = p;
61
      while (current != nullptr) {
          ancestors.insert(current);
          current = parent[current];
      }
66
      current = q;
68
      // The first node from q's ancestor chain
      // already seen from p is the LCA.
      while (
          ancestors.find(current)
          == ancestors.end()
      ) {
          current = parent[current];
      }
77
      return current;
  }
80};
81
82int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(5);
  root->right = new TreeNode(1);
  root->left->left = new TreeNode(6);
  root->left->right = new TreeNode(2);
  root->right->left = new TreeNode(0);
  root->right->right = new TreeNode(8);
  root->left->right->left = new TreeNode(7);
  root->left->right->right = new TreeNode(4);
92
  TreeNode* p = root->left;
  TreeNode* q = root->left->right->right;
95
  Solution solution;
97
  TreeNode* lca =
      solution.lowestCommonAncestor(root, p, q);
100
  cout << lca->val << endl;
102
  return 0;
104}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N). Building the parent mapping using BFS may require visiting all N nodes. Traversing the ancestor chains of p and q requires at most O(H) additional time.

Space Complexity: O(N), where N is the number of nodes in the binary tree. The parent mapping may store every node, while nodesQueue and the ancestors set can also require additional linear space in the worst case.

Optimal Approach

The LCA can be found without storing complete root-to-node paths or explicit parent relationships.

For every recursive call, the following question is considered:

Does this subtree contain p, q, or their LCA?

Two variables, leftResult and rightResult, are used to store what is returned from the left and right subtree searches. These names make their purpose explicit: each variable represents useful information discovered within its respective subtree.

If the current node is p or q, that node is returned upward because one of the required targets has been found and may itself become the LCA.

If both leftResult and rightResult are non-null, one target has been found on each side. Therefore, the current node is the deepest point where the two branches meet.

If only one result is non-null, that result is propagated upward because both targets may lie in that branch, or one target may be an ancestor of the other.

Algorithm

If the current node is null, null is returned because the subtree contains neither target.
If the current node is equal to p or q, the current node is returned because one target has been found and may itself be the Lowest Common Ancestor.
The result of searching the left subtree is stored in leftResult, while the result of searching the right subtree is stored in rightResult, so information found in both branches can be compared.
If both leftResult and rightResult are non-null, the current node is returned because the two target nodes have been found in different branches.
If only leftResult is non-null, it is propagated upward because the useful result lies in the left subtree.
Otherwise, rightResult is propagated upward because the useful result lies in the right subtree or neither target has been found.

Dry Run

Lowest Common Ancestor Optimal Approach Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int value) {
      val = value;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17public:
  // Returns p, q, or their LCA
  // when found inside the current subtree.
  TreeNode* lowestCommonAncestor(
      TreeNode* root,
      TreeNode* p,
      TreeNode* q
  ) {
      if (root == nullptr) {
          return nullptr;
      }
28
      // A target node may itself
      // be the Lowest Common Ancestor.
      if (root == p || root == q) {
          return root;
      }
34
      // leftResult and rightResult capture
      // useful nodes found in each subtree.
      TreeNode* leftResult =
          lowestCommonAncestor(
              root->left,
              p,
              q
          );
43
      TreeNode* rightResult =
          lowestCommonAncestor(
              root->right,
              p,
              q
          );
50
      // Non-null results from both sides mean
      // the targets lie in different branches.
      if (
          leftResult != nullptr &&
          rightResult != nullptr
      ) {
          return root;
      }
59
      // A single non-null result is propagated
      // upward until another target is found.
      if (leftResult != nullptr) {
          return leftResult;
      }
65
      return rightResult;
  }
68};
69
70int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(5);
  root->right = new TreeNode(1);
  root->left->left = new TreeNode(6);
  root->left->right = new TreeNode(2);
  root->right->left = new TreeNode(0);
  root->right->right = new TreeNode(8);
  root->left->right->left = new TreeNode(7);
  root->left->right->right = new TreeNode(4);
80
  TreeNode* p = root->left;
  TreeNode* q = root->left->right->right;
83
  Solution solution;
85
  TreeNode* lca =
      solution.lowestCommonAncestor(root, p, q);
88
  cout << lca->val << endl;
90
  return 0;
92}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited at most once during the recursive traversal.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Interview follow-up Questions

Yes. If one target node is an ancestor of the other, that node is the LCA. For example, if p = 5 and node 4 lies inside the subtree of 5, then the LCA of 5 and 4 is 5.

Lowest Common Ancestor in a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree

Lowest Common Ancestor in a Binary Tree

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Can one of the given nodes itself be the LCA?

Why does the recursive approach return the current node when both subtree results are non-null?

Why is a single non-null result propagated upward?

Is the Lowest Common Ancestor necessarily the root?

Which approach is generally preferred?

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree