Binary Search Tree traversal - Find Closest Value

Question

Im working on a AlgoExpert challenge, I already dedicated time to solving it on my own, watched the video lecture on it and I feel like I have a good understanding, but my skills with recursion and Tree traversal are pretty low right now (that's why I'm working on it).

This is the prompt

Write a function that takes in a Binary Search Tree (BST) and a target integer value and returns the closest value to that target value contained in the BST. Each BST node has an integer value, a left child node, and a right child node. Its children's are valid BST nodes themselves or None / Null

TARGET: 12

This is my solution so far:

function findClosestValueInBst(tree, target) {
    let closest = tree.value;
  const traverse = (inputTree) => {
        if (inputTree === null) return;
        if (Math.abs(target - closest) > Math.abs(target - inputTree.value)) {
            closest = inputTree.value;
        }
        
        if (target < tree.value) {
            console.log('left')
            traverse(inputTree.left)
        } else {
            console.log('right')
            traverse(inputTree.right)
        }
        
    }
    traverse(tree)
    return closest;
}

// This is the class of the input tree. Do not edit.
class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

The behavior so far is, traverse to Node 15, but then, instead of going to 13, it goes to 22 so it returns 10 as the closes possible value instead of 13 which has an absolute value closer to 12 than 10.

Answer 1

function findClosestValueInBst(tree, target) {
    let closest = tree.value;
  const traverse = (inputTree) => {
        if (inputTree === null) return;
        if (Math.abs(target - closest) > Math.abs(target - inputTree.value)) {
            closest = inputTree.value;
        }
        // As you can see below this line you are checking target < tree.value
        // problem is that tree is the root that your surrounding function gets
        // not the argument that your recursive function gets.
        // both your condition and your parameter to traverse
        // need to be inputTree, not tree
        if (target < tree.value) {
            console.log('left')
            traverse(inputTree.left)
        } else {
            console.log('right')
            traverse(inputTree.right)
        }
        
    }
    traverse(tree)
    return closest;
}

Now look at the code below:

function findClosestValueInBst(root, target) {
    let closest = root.value;
  const traverse = (node) => {
        if (node === null) return;
        if (Math.abs(target - closest) > Math.abs(target - node.value)) {
            closest = node.value;
        }
        
        if (target < node.value) {
            console.log('left')
            traverse(node.left)
        } else {
            console.log('right')
            traverse(node.right)
        }
        
    }
    traverse(root)
    return closest;
}

In such cases it is helpful to name the parameters more distinct so that no confusion arises.