Lowest Common Ancestor in Binary Tree | Dataford Interview Questions

Find LCA in a binary tree. Come up with your own test cases and find corner cases.

Asked in the Loop interview 5 stage. Implement the solution for a general binary tree, not a binary search tree.

I/O Contract

Implement lowest_common_ancestor(root, p, q), where root is a nested dictionary with keys val, left, and right, or None. The values p and q identify two node values. Return the integer value of their lowest common ancestor, or None when the tree is empty.

Example 1: root = {"val": 3, "left": {"val": 5, "left": null, "right": null}, "right": {"val": 1, "left": null, "right": null}}, p = 5, q = 1 returns 3.

Example 2: In a tree where 5 is an ancestor of 4, p = 5, q = 4 returns 5.

Constraints

Each node is represented as a dictionary with keys val, left, and right, or as None.
Node values are unique integers.
p and q are present in every non-empty tree.
The tree may be empty or skewed.

Function Signature

def lowest_common_ancestor(root, p, q):

Your question is Lowest Common Ancestor in Binary Tree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem