Neural Mastery
← Practice
Lowest Common Ancestor of a Binary Treemedium

Lowest Common Ancestor of a Binary Tree

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Graph & Tree Traversal, Step by Step
Structure
Algorithm
ABCDE
visiting A -> visited order so far: [A]
queue now: [B, C]
Step 1 / 5
Both modes run the real algorithm from the linked practice problem, one step at a time -- edit the graph or pick different tree nodes and every step recomputes live.

Find the lowest common ancestor of two nodes in an arbitrary binary tree without BST ordering guarantees.

Related Skills

Task

Implement lowest_common_ancestor_bt(root, p, q): perform a bottom-up postorder traversal. If a node matches p or q, return it. If both left and right recursive calls return non-null nodes, the current node is the LCA.

Function Signature

lowest_common_ancestor_bt(root: dict, p: int, q: int) -> int

Examples

Example 1: p and q in Different Subtrees
Input: root = {'val': 3, 'left': {'val': 5, 'left': {'val': 6, 'left': None, 'right': None}, 'right': {'val': 2, 'left': {'val': 7, 'left': None, 'right': None}, 'right': {'val': 4, 'left': None, 'right': None}}}, 'right': {'val': 1, 'left': {'val': 0, 'left': None, 'right': None}, 'right': {'val': 8, 'left': None, 'right': None}}} p = 5 q = 1
Output: 3
Example 2: LCA is One of the Nodes
Input: root = {'val': 3, 'left': {'val': 5, 'left': None, 'right': {'val': 4, 'left': None, 'right': None}}, 'right': {'val': 1, 'left': None, 'right': None}} p = 5 q = 4
Output: 5

Constraints

  • Number of nodes in the tree is in range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p and q exist in the tree and p != q.
Python3Saved ✓
def lowest_common_ancestor_bt(root: dict, p: int, q: int) -> int:
"""root: binary tree root node as {'val', 'left', 'right'}.
p, q: values of two distinct nodes guaranteed to be in the tree.
Return the value of the Lowest Common Ancestor (LCA) node."""
# Your implementation here
pass

Case 1: p and q in Different Subtrees
Input: root = {'val': 3, 'left': {'val': 5, 'left': {'val': 6, 'left': None, 'right': None}, 'right': {'val': 2, 'left': {'val': 7, 'left': None, 'right': None}, 'right': {'val': 4, 'left': None, 'right': None}}}, 'right': {'val': 1, 'left': {'val': 0, 'left': None, 'right': None}, 'right': {'val': 8, 'left': None, 'right': None}}} p = 5 q = 1
Expected: 3
Case 2: LCA is One of the Nodes
Input: root = {'val': 3, 'left': {'val': 5, 'left': None, 'right': {'val': 4, 'left': None, 'right': None}}, 'right': {'val': 1, 'left': None, 'right': None}} p = 5 q = 4
Expected: 5