Closest Value in a BST with Recursion

I recently had the pleasure of graduating from Grace Hopper Academy, a coding bootcamp in New York City. Post graduation, my classmates and I formed a group to continue practicing data structure algorithms. This group has been indispensable for me. Not only am I reinforcing my understanding of data structures, but I get to do so alongside some of the best and the brightest.

This week, my friend Yumi and I are leading the group through a binary tree problem. Our prompt, inspired by an AlgoExpert problem, is the following:

Given a binary search tree and a target value, return the value in the tree closest to the target.

The Rules

The regular BST rules apply: lower values on the left, equal or greater values on the right. Child nodes are themselves trees or null. To make this simpler, we will make a one more assumption. Our tree will have just one “closest value” to return. Let’s begin.

Look at the example above. We know the answer is 13 at a glance. But to find our algorithm we will step through the logic.

The Logic

We start at the root node. The closest value so far is the only node we have visited: the root, with a value of 12. But we need to take a look at the rest of the tree to know if this is the closest value overall.

We know that lower values lie to the left, but our target is greater than the current node’s value. So we must increment to the right. This small step is valuable: we managed to eliminated half of the tree by comparing our target with the current node and deciding which node to visit next.

So we move to the right. This node has a value of 23, which is 9 away from our target of 14. This is worse than the root node. What does this tell us? Well, it tells us that we need a way to hold our history. We will have to traverse a bunch of nodes in this tree, and not all of them are important to us. We will need to remember the best node so far in the traversal. So we are at the node with value 23, holding on to our memory of the value 12. Let’s keep moving.

Our target is less than our current value, so we must increment to the left. Now we will evaluate the node and increment accordingly, just like before. If this feels familiar, it’s because we have already established a pattern. And where there is a pattern, you can write an algorithm.

The Code

If we keep going our path will look like this.

To review:

• We must traverse a path of the tree from root to leaf node
• That path is based on how the target compares to our current node - if the target is lower, move to the left, otherwise move to the right
• We must keep a history of what the best, or closest, node has been so far

This problem can be solved iteratively. But it can also be solved recursively. I detail this approach below.

function findClosestVal(tree, target, closest = Infinity) {
  if (tree === null) {
    return closest
  } 
  else {
    if (Math.abs(tree.val - target) < Math.abs(closest - target)) {
      closest = tree.val
    }
    if (target < tree.val) {
      return findClosestVal(tree.left, target, closest)
    } else {
      return findClosestVal(tree.right, target, closest)
  }
}

The Complexity

Time to evaluate the time and space complexity. Assuming a balanced tree, we will visit log(n) nodes on the path from root to leaf. At each node, we add a call to the callstack. This makes both our time complexity and our space complexity O(log(n)).

For an unbalanced tree, how does this change? We can imagine the utmost unbalanced tree where every node only has a right child. In this case, a path from root to leaf would touch every single node. That makes both time and space complexity O(n).

For this problem the iterative approach is a more optimal solution. You will traverse the same number of nodes, but without adding to the callstack and therefore the space complexity.

Still, this recursive solution is a good thought experiment. Stay tuned for future algorithm walkthroughs.

Until next time, I will make like a binary tree and leave.