MediumCoding

Find the lowest common ancestor (LCA) of two nodes in a binary tree.

Asked at

Apple

Meta

Oracle

Spotify

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Reference answer

To find the Lowest Common Ancestor (LCA) of two nodes p and q in a Binary Search Tree (BST), you can traverse the tree starting from the root. At each node, compare the values of p and q with the current node's value:

If both p and q are smaller than the current node, the LCA must be in the left subtree. Move to the left child.
If both p and q are larger than the current node, the LCA must be in the right subtree. Move to the right child.
Otherwise (if one is smaller and one is larger, or if one of them is equal to the current node), the current node is the LCA. This is because the paths to p and q diverge at this node.

If you reach a null node without finding the LCA, it implies an issue with the input or tree structure, and you would typically return null.

Hiring now

LinkedIn has 196 open roles right now

Also hiring: Spotify

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Lead Account Executive, Large Customer, Financial Services - LinkedIn Marketing Solutions
Chicago, IL, United States
Director, LinkedIn Pulse Digital Platform
New York, NY, United States

Or practice this question first

Next question