Find Closest Value in Binary Search Tree?-CodePudding

I have this algorithm structure problem; write a function that takes in a BST and a target interget value and returns the closet value to that target value contained in the BST.

The algorithm site gave me this to work with;

function findClosestValueInBst(tree, target) {
  // Write your code here.
}

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

I am not asking for the answer but how can I test this out in my local visual studio code? What values do i need to pass in the tree/target argument parameters of the function for me to even test things or console.log things out?

I guess they are giving me an example input but.. how can i even log this to my function to test it?

  {
  "tree": {
    "nodes": [
      {"id": "10", "left": "5", "right": "15", "value": 10},
      {"id": "15", "left": "13", "right": "22", "value": 15},
      {"id": "22", "left": null, "right": null, "value": 22},
      {"id": "13", "left": null, "right": "14", "value": 13},
      {"id": "14", "left": null, "right": null, "value": 14},
      {"id": "5", "left": "2", "right": "5-2", "value": 5},
      {"id": "5-2", "left": null, "right": null, "value": 5},
      {"id": "2", "left": "1", "right": null, "value": 2},
      {"id": "1", "left": null, "right": null, "value": 1}
    ],
    "root": "10"
  },
  "target": 12
}

CodePudding user response：

You need to build valid search tree.

At first implement operation Add(root, value)

Then make operations Find that looks for exact coincidence, and Successor and Predecessor to get closest values larger and smaller than current one.

Then provide sequence of values to make a tree (example: 6,3,9,0,15,5,7,14) and test above functions.

To implement findClosestValueInBst, you can modify the code of Find but when you discover element absence (standing at the last tree leaf), call one of Successor or Predecessor function to check a neighbor and find what value is close to target.

CodePudding user response：

Hints:

Think about how things could go wrong. Typical mistakes are

gross programming errors (binary search plain wrong, typos);
subtle limit cases (empty tree, tree of a single node, two nodes; equal nodes; target equal to a node, target in the middle; binary search wrong on few nodes...).

For each of those situations, how can you check ?

Rather than only trying a few test cases, I would advise to instrument the code with assertions that you know must hold at strategic places. For instance, check that the solution is still found among the subtrees that you consider.

Also make sure to implement a bulletproof function that returns the correct answer in all cases (efficiency does not matter).

As the exercise does not seem to be about how to build a BST, it is acceptable to copy existing code for this part of the task. Make sure that the source is reliable. (For double safety, you can validate the trees that are built.)

CodePudding user response：

You probably want to build your own BST (or a few) to test your code out. You could build them by hand by just creating a bunch of nodes one by and and linking them together, or write an insert function to pass values in to and build your trees like that. You could use an array of values and map over it to build nodes if you'd like. Just keep track of the root node for your BST(s).

Then call your function with a root of a BST that you've created and several different target values. See if your function returns the value you'd expect. Try to cover all common and edge cases:

target is exactly in the tree: as the root node, an internal node, or a leaf node;

target not in the tree but is between two values (see that you return the closer one);

target not in the tree and larger or smaller than everything in the tree (see that you return the max or min value actually in the tree);

handle searching in an empty BST, a BST with just one node, BSTs with and without duplicate values

edit: Added some boilerplate code to build a BST from a list of values, and then an example how you would pass the tree to your function and log the output. There's also a function to print a tree to the console. It's on its side and you have to imagine the links but it could be helpful. Good luck

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

function findClosestValueInBst(tree, target) {
  // Write your code here.
}

// build a BST from an array of values and return the root
function buildTree(values) {
  let root = null
  for (let value of values) root = insert(root, value)
  return root;
}
// insert a value into a BST
function insert(root, value) {
  if (!root) return new BST(value)
  if (value < root.value) 
    root.left = insert(root.left, value)
  else 
    root.right = insert(root.right, value)
  return root
}
// display a binary tree
function display(root, depth = 0) {
  if (!root) return;
  display(root.right, depth 1)
  console.log(`${'\t'.repeat(depth)}${root.value}`)
  display(root.left, depth 1)
}

const T1 = buildTree([
  10,  7,  2, 13, 10,  3,
   5, 12, 16, 23,  1, 20
])
display(T1)

// console.log(findClosestValueInBst(T1, 12)) // should return 12, because 12 is in T1
// console.log(findClosestValueInBst(T1, 14)) // should return 13, as it's the closest to 14