Closest Common Ancestor in Binary Tree

Given two values in a binary tree, write a function findClosestAncestor that finds the closest ancestor node relative to these target nodes.

You will be given a root as the input along with the values of two nodes that exist in the tree. The tree contains only unique integers, and the child values will always be different.

It's important to note that this is a binary tree and not a BST where the value of the node could indicate its position as an ancestor or where to search for the children.

The tree nodes will use the following implementation:

Breakdown

Approach and test strategy

Lowest common ancestor by subtree membership and node identity

Read the approach, boundary cases, and complexity

Find the deepest input-tree node that is an ancestor of both targets. A target may itself be the answer when the other target lies below it. In a general binary tree, value order does not tell you which subtree contains a target; a binary-search-tree shortcut would require a different contract. Return a reference to the original tree node, not a freshly allocated node with equal data.

Cases to check

Place targets on opposite sides of the root.
Make one target an ancestor of the other.
Use an unbalanced tree and verify that the returned node belongs to the input tree.

Cost model

A full subtree search takes O(n) time with O(h) recursive stack space. If the contract changes to permit absent targets, the implementation must also establish whether both were found.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

Follow teacher

Table of Contents

Validate My Answer

This can be solved iteratively or recursively. Let's go ahead and assume you don't need to worry about stack overflows if you're interested in solving it recursively. That's the solution I'll be showing.
A node can be the common ancestor with itself and a child node.
At worst, the root is the common ancestor for all nodes.
This can be solved in O(n) time and space.

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {BinaryNode} root
 * @param {int} firstChildValue
 * @param {int} secondChildValue
 * @return {BinaryNode}
 */
const findClosestAncestor = (root, firstChildValue, secondChildValue) => {
  // Your solution here
}