LCA with Parent Pointers

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is LCA with Parent Pointers. 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.

You need to log in / sign up to run or submit.

Problem

Lowest Common Ancestor of a Binary Tree (LC 1650 variant where nodes have parent pointers), solve in Time O(depth) and Space O(1).

Asked in the Phone Screen stage. The tree is represented by a parent-pointer mapping for grading: parent[node] gives a node's parent, and the root has no entry or maps to null.

Input and Output

Implement lowest_common_ancestor(parent, p, q). Return the node identifier representing the lowest common ancestor of p and q. The nodes belong to the same binary tree.

Constraints

The parent mapping represents one binary tree.
The root has no parent entry or has a parent value of null.
p and q are valid node identifiers in the same tree.
The node identifiers are non-null and hashable.
Use O(depth) time and O(1) auxiliary space.

Function Signature

def lowest_common_ancestor(parent, p, q):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output