# 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.

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.

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

}

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…

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.