CODEWITHSUNDEEP
javascriptbinary-search-tree
dsp_099
dsp_099

Reputation: 6121

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

sample BST structure

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
}

Upvotes: 0

Views: 499

Answers (1)

S. Strempfer
S. Strempfer

Reputation: 298

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))
}

Upvotes: 1

Related Questions