Closest Common Ancestor in Binary Tree Coding Interview Question | Skilled.dev
Interview Question

Closest Common Ancestor in Binary Tree

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

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

You will be given a root as the input along with 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 search for children.

       9
      / \
     5   4
    / \   \
   1   7   3
  / \       \
 42  10      2

findClosestAncestor(root, 10, 7); // 5

The tree nodes will use the following implementation:

class BinaryNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

Validate My Answer

  1. This can be solved iteratively or recursively. Let's go ahead and assume you don't need to worry about stackoverflows if you're interested in solving it recursively. That's the solution I'll be showing.

  2. A node can be the common ancestor with itself and a child node.

  3. At worst, the root is the common ancestor for all nodes.

  4. This can be solved in O(n) time and space.