Returning a value at the end of a recursive binary search tree traversal in JavaScript

Question

I need to traverse a BST and return the node value that is closest to the supplied target integer value.

The traversal can be done as follows:

function traverse(node, target, closestValue) {
    console.log(node.value);
    let potentialClosestValue = Math.abs(node.value - target)
    if (potentialClosestValue < closestValue) { closestValue = potentialClosestValue; }
    
    if (node.left) {
        traverse(node.left, target, closestValue)
    }
    if (node.right) {
        traverse(node.right, target, closestValue)
    }
}

function findClosestValueInBst(tree, target) {
    traverse(tree, target, Infinity)
}

How do I know that the entire tree traversal has finished? I can create a variable out of scope of the traverse function and return that, but can I return it from the recursive function somehow? e.g.:

function findClosestValueInBst(tree, target, output) {
    return traverse(tree, target, Infinity, 0) // returns 13
}

Can't you just have the traverse function return the closest value from left and right? — S. Strempfer
– S. Strempfer, Commented Jul 14, 2020 at 1:52

S. Strempfer · Accepted Answer · 2020-07-14 01:59:58Z

1

function traverse(node, target, closestValue) {
    console.log(node.value);
    let potentialClosestValue = Math.abs(node.value - target)
    if (potentialClosestValue < Math.abs(closestValue - target)) { closestValue = node.value; }
    
    if (node.right) {
        let res = traverse(node.right, target, closestValue)
        if (Math.abs(res-target) < Math.abs(closestValue - target) closestValue = res
    }
    if (node.left) {
        let res = traverse(node.left, target, closestValue)
        if (Math.abs(res-target) < Math.abs(closestValue - target) closestValue = res 
    }
    return closestValue
}

function findClosestValueInBst(tree, target) {
    console.log(traverse(tree, target, Infinity))
}

answered Jul 14, 2020 at 1:59

S. Strempfer

2982 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

dsp_099 Over a year ago

Cheers. That works. It's bending my brain a little bit though. So, traverse() now returns closestValue every single time, BUT for each left & right nodes it re-calculates the value of closestValue? I am having a hard time seeing why it doesn't return on the first iteration.

S. Strempfer Over a year ago

It does, but before the first iteration can return all the recursive calls have to finish, it traverses the whole tree. That's how recursive functions work. It basically traverses the tree from bottom to top logically.

Collectives™ on Stack Overflow

Returning a value at the end of a recursive binary search tree traversal in JavaScript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related