Skip to main content

236. Lowest Common Ancestor of a Binary Tree

mediumAsked at Juniper Networks

Find the lowest common ancestor of two nodes in a binary tree using recursive post-order traversal. Juniper applies this to hierarchical network configuration trees — finding the most-specific policy node that governs both a source and destination interface requires exactly this LCA traversal.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2025-Q3)— Cited in Juniper SWE onsite reports as a tree traversal problem with hierarchical reasoning context.
  • Blind (2025-08)— Juniper candidates list LCA as a medium tree problem that appears in networking software roles.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA: 'The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).'

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • −10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • Both p and q will exist in the tree.

Examples

Example 1

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

Explanation: 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: LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself.

Approaches

1. Recursive post-order DFS

Post-order recursion: search left and right subtrees. If a node is p or q, return it. If both children return non-null, the current node is the LCA. If only one returns non-null, propagate that result upward.

Time
O(n)
Space
O(h) call stack, h = tree height
function lowestCommonAncestor(root, p, q) {
  if (root === null) return null;
  if (root === p || root === q) return root; // found one of the targets
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left !== null && right !== null) return root; // p in left, q in right
  return left !== null ? left : right; // propagate the found node upward
}

Tradeoff: O(n) time, O(h) space. Elegant single-pass post-order traversal. The insight is that returning a node indicates 'p or q (or their LCA) is in this subtree.'

Juniper Networks-specific tips

Walk through the recursion logic carefully — Juniper interviewers will trace through an example. The key insight to articulate is: 'If I find p in the left subtree and q in the right subtree (or vice versa), the current node must be the LCA. If I find both in the same subtree, propagate the LCA upward from that subtree.' Mention the special case: a node can be the LCA of itself and its descendant — handled by the root === p || root === q early return.

Common mistakes

  • Not handling the case where a node is the ancestor of itself — the early return (root === p || root === q) must come before recursing into children.
  • Assuming the tree is a BST and using the BST LCA shortcut — this tree is a general binary tree, not a BST.
  • Recursing into children even after finding p — the early return prevents unnecessary traversal.
  • Checking node values instead of node references — the problem guarantees unique values but reference comparison is safer and more direct.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • LCA of a Binary Search Tree (LC 235) — simpler because BST ordering allows a guided search.
  • LCA with parent pointers (LC 1650) — two-pointer approach using path lengths.
  • How would you find the most-specific policy node governing two interfaces in a hierarchical Junos configuration?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What does returning root mean when both left and right are non-null?

It means p was found in one subtree and q in the other. The current node is the split point — and therefore the LCA.

What if one of the targets is an ancestor of the other?

The early return (root === p || root === q) fires first, returning the ancestor before recursing further. The ancestor is correctly identified as the LCA.

Is this approach valid for a general binary tree (not a BST)?

Yes — it does a full post-order traversal of the entire tree without relying on any ordering property.

Practice these live with InterviewChamp.AI

Drill Lowest Common Ancestor of a Binary Tree and other Juniper Networks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →