CoDEVIANT #15 (10/2/20) — The Spookiest Halloween Yet…

So I broke down and subscribed to AlgoExpert.io…

Thing is, I don’t have a CS degree. I have two diplomas certifying me as being highly trained in yelling prettily at people while dressing up and pretending to be someone that I’m not on stage. And while I graduated from a really great coding bootcamp, encountering the kinds of ‘in the interview’ coding problems (which typically aren’t like the ones you’ll find on the job — at least in my limited experience) make my head feel like it’s going to explode. I start to feel my fight or flight instincts kick in. Generally not being someone to run puts me in a position where I want to deck somebody.

• This will likely NOT get you the job and will get you in jail, where you have no choice BUT to fight.

…unless you wanna end up somebody’s bitch.

Anywho….let’s get to our problem for the day.

— — — — — — — — — — — — — -

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. You can assume that there will only be one closest value. Each BST node has an integer value, a left child node, and a right child node.

A node is a valid BST node if it’s value is greater than the values of every node to its left, and is lesser than the values of every node to its right. A node’s children nodes are either valid BST nodes or None/null.

— — — — — — — — — — — — — —

So I had no clue how to do this, but I got some help and I’m going to share the pearls of wisdom about how to do this.

Sometimes, that’s just how it is, chief.

So let’s assume our target is 16 and our tree is like this

example of tree in code:

treeNode = {
   this.value = 10,
   this.left = {
     value: 5,
     left: { value: 2, left: [BinaryTree], right: null },
     right: { value: 5, left: null, right: null }
   },
   this.right = {
     value: 15,
     left: { value: 13, left: null, right:[BinaryTree] },
     right:  { value: 22, left: null, right: null }   
   }
}

We’re going to run a function that accepts the tree and the target. Inside this function we return another function we’re going to write which takes three arguments:

• tree
• target
• closest

I called this method snoopsTreeFriend. In the main function, we return snoopsTreeFriend with the three values for the arguments:

• tree / tree
• target / 16
• closest / tree.value (in this case at the top it is 10)

First of all, if tree equals null, then we return the value that was passed in for closest.

if(tree == null) {
   return closest
}

If there’s no tree, there’s nothing for me.

So what we’re going to do is get the absolute-value of the target MINUS the closest and the absolute-value of the target MINUS the tree.value. If the former is larger than the latter, closest becomes the latter. We’re basically finding the candidate for closest (between closest and tree.value) that is fewer negative or positives spaces away from the target

if(Math.abs(target - closest) > Math.abs(target - tree.value)) {
  closest = tree.value
 }

Now we do some cool comparison work. We compare the target to the current tree.value

If the target is LESS than the tree.value, we return the function we are running ‘snoopsTreeFriend’ and pass in tree.left as tree, target as target, and closest as closest.

Else, if the target is MORE than the tree.value, we return the function we are running ‘snoopsTreeFriend’ and pass in tree.right as tree, target as target, and closest as closest.

Else, we return closest.

if(target < tree.value) {
  return snoopsTreeFriend(tree.left, target, closest)
 } else if (target > tree.value) {
  return snoopsTreeFriend(tree.right, target, closest)
 } else {
   return closest
 }

That’s right kids…

It’s recursion time!

So let’s take a look at all of our function snoopsTreeFriend.

function snoopsTreeFriend(tree, target, closest) {
 if(tree == null) {
   return closest
 }
 if(Math.abs(target - closest) > Math.abs(target - tree.value)) {
   closest = tree.value
 }
 if(target < tree.value) {
  return snoopsTreeFriend(tree.left, target, closest)
 } else if (target > tree.value) {
  return snoopsTreeFriend(tree.right, target, closest)
 } else {
   return closest
 }
}

The beauty of this is that the comparison between target and tree.value is going to go on and keep calling our method until it can’t anymore, and at that point it will return closest. And we’ll have our answer.

It’s been a LONG time since I worked with Binary Search Trees, so I’m glad to have a nice, solid, and digestible strategy for dealing with them.

Anyways, take it sleazy and I’m outta here.

Slight exaggeration of me running away to do something frivolous like playing video games or doomscrolling while having Netflix play on my phone.