Skip to content

Instantly share code, notes, and snippets.

@jchiatt

jchiatt/findClosestInBst.js

Created November 2, 2020 16:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jchiatt/e5083d4e9ee620f6c1bf58945843aa37 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jchiatt/e5083d4e9ee620f6c1bf58945843aa37 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. jchiatt created this gist Nov 2, 2020.
    26 changes: 26 additions & 0 deletions findClosestInBst.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,26 @@
    function findClosestValueInBst(tree, target) {
    return findClosestValueRecursive(tree, target, tree.value);
    }

    function findClosestValueRecursive(tree, target, closest) {
    if (!tree) return closest;
    if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
    closest = tree.value;
    }
    if (target < tree.value) {
    return findClosestValueRecursive(tree.left, target, closest);
    }
    if (target > tree.value) {
    return findClosestValueRecursive(tree.right, target, closest);
    }

    return closest;
    }

    class BST {
    constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    }
    }