Quick Overview

This question evaluates understanding of binary tree structure, lowest common ancestor concepts, and competency in algorithmic reasoning and tree traversal within the Coding & Algorithms category.

Find lowest common ancestor

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question LeetCode 236. Lowest Common Ancestor of a Binary Tree — Given a binary tree, find the lowest common ancestor (LCA) of two given nodes. Follow-up: how would the solution change if each node had a parent pointer? https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

Overview: This question evaluates understanding of binary tree structure, lowest common ancestor concepts, and competency in algorithmic reasoning and tree traversal within the Coding & Algorithms category.

Given a binary tree represented as a 0-indexed level-order array using null for missing nodes, return the value of the lowest common ancestor (LCA) of two distinct node values p and q. The LCA is the deepest node that has both p and q as descendants (a node can be a descendant of itself). The array follows complete-binary-tree indexing: for any index i, the left child is at 2*i+1 and the right child is at 2*i+2 when within bounds; missing nodes must be represented by null in those positions. Trailing nulls beyond the last non-null index may be omitted. All node values are unique, and both p and q are guaranteed to exist in the tree.

Constraints

  • 1 <= n <= 200000 where n is the length of level
  • All node values are unique integers
  • Both p and q exist in the tree and p != q
  • The tree uses complete-binary-tree indexing with null placeholders; trailing nulls past the last non-null index may be omitted
  • Values fit in 32-bit signed integers

Hints

  1. Recursive approach: if the current node is p or q, return it; otherwise recurse on left and right. If both sides return non-null, current node is LCA; else propagate the non-null result.
  2. Iterative approach: compute parent pointers by scanning the array using 2*i+1 and 2*i+2 indices. Then mark all ancestors of p, and climb from q until you hit a marked ancestor.
  3. If each node had a parent pointer, you could directly mark ancestors of p and ascend from q without building the tree.

Loading coding console...

Show the approach

Approach

We avoid recursion by computing parent pointers directly from the level-order array using complete-binary-tree indexing. After building a map from each node value to its parent's value, we collect all ancestors of p up to the root in a set. Then we climb from q toward the root until we first encounter a value present in that ancestor set; that value is the LCA. This mirrors the classic approach when nodes have parent pointers and works in linear time.

Time complexity:
O(n)
Space complexity:
O(n)