Binary Tree Problem Solving | Dataford Interview Questions

Your question is Binary Tree Problem Solving. Start with the requirements on the right.

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

Problem

Handshake represents an organization hierarchy as a binary tree for this exercise. Given the tree root and two distinct node values, return the value of their lowest common ancestor, the deepest node that contains both targets in its subtree.

Formal Specification

Implement lowest_common_ancestor(root, p, q).

root is either None or a nested dictionary with the shape {"val": integer, "left": node_or_none, "right": node_or_none}.
p and q are distinct integer values that occur exactly once in the tree.
Return the integer value of the lowest common ancestor.
A node is considered an ancestor of itself, so if one target is the parent of the other, return the parent value.

Constraints

1 <= number of nodes <= 10^5
Node values are unique integers
Both target values occur exactly once in the tree
The tree may be balanced or completely skewed
The root is either None or a nested node dictionary

Function Signature

def lowest_common_ancestor(root, p, q):