Lowest Common Ancestor in Binary Tree | Dataford Interview Questions

Pine Labs models certain payment workflow relationships as a binary tree. Given the root of a binary tree and two distinct node values, find their lowest common ancestor (LCA), the deepest node that is an ancestor of both target nodes.

Implement lca(root, p, q) and return the LCA node's integer value. Each node is represented as a dictionary with a unique value key and optional left and right child dictionaries. Both target values are guaranteed to exist in the tree.

Formal Specification

Input: root, a nested dictionary representing the binary tree, and integers p and q representing target node values.
Output: The integer value of the lowest common ancestor of p and q.
A node is considered an ancestor of itself for this problem.

Constraints

1 <= number of nodes <= 10^5
Node values are unique integers
p and q are distinct values present in the tree
The tree may be skewed

Function Signature

def lca(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

Formal Specification

Input: root, a nested dictionary representing the binary tree, and integers p and q representing target node values.
Output: The integer value of the lowest common ancestor of p and q.
A node is considered an ancestor of itself for this problem.

Constraints

1 <= number of nodes <= 10^5
Node values are unique integers
p and q are distinct values present in the tree
The tree may be skewed

Function Signature

def lca(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.