More data structures! Trees

I love redwoods. someday I’d like to visit these beauties!

Yikes, there is just so much to learn and so little time when you’re already working a busy full time job! TBH I am getting a wee bit bored with this intro to computer science stuff and would rather get back to straight up coding, but I promised myself I’d get through this intro course (and write about it) before I really get back into any major coding projects. I don’t want to be caught off guard again at my next coding challenge! So, trees it will be. But no not redwoods — actually they’re not even a great example in this case, you’ll see why in a minute.

What I am talking about here looks more like this:

see any patterns?

Before I even get into binary search and how I implemented one using JavaScript, let’s look at some of the details of trees:

Yeah, I promise we are still talking about the second kind. But I love the fun names someone even nerdier than me must have given the various aspects of this data structure many years ago! What do they mean in this context?

The words I bolded above — parent, child, sibling — are all ways of communicating relationships within a tree. The root, branch and leaf describe the pieces that connect it. In a plain old tree, a parent can have tons of children, but in a binary search tree each parent can only have two or three children.

In a binary search tree like the graphic above, the lower half of all values has to be on the left side of the tree (left children) and the higher values go on the right (right children). This makes loading more efficient.

Nodes in this type of tree all have the following properties: data, depth (to indicate what level of the tree it is on), a left pointer and a right pointer (hi, doubly linked lists). These values, if put into array form, are split right down the middle. If it’s an even number of elements in the array, you split by the lower of the two middle values.

If you’re writing a function to search for a value in a tree, how do you find that middle index? Pretty easily, you just average the first and last index. The first index is always 0, and the last can be determined by checking the length property of an array:

const arr = [23, 24, 55, 64, 98, 101, 212, 240, 900]
let lowest = 0
let highest = arr.length //in this case 9
let middle = Math.floor(highest + lowest / 2) // you want the Math.floor so you don't end up with a decimal.

If you’re lucky, the value you’re searching for will be the index and your function has done it’s job with the following simple code:

const check = arr[middle]if(check === yourSearchedForValue){
return middle
}

But I’m not usually lucky, so, onward.

while(lowest < highest) {
if(check === yourSearchedForValue){
return middle;
} else if (yourSearchedForValue > check) {
lowest = middle + 1 ///increments the count from the middle up one
} else {
highest = middle {
}
}

What have we done here? We checked the other values. Using a while loop (while lowest is less than highest). Then we use an if/else if statement to check if the middle index is the target (same as in the previous example), if it is, great, return it. If it isn’t, and the target is still greater than that middle index’s value, increment middle by one. If it isn’t, and the target is less than the middle index’s value, set the highest to ‘middle’. You’re basically breaking the array in two here, and doing so repeatedly until you have an answer.

A binary search tree in action!

I actually did find this topic pretty interesting because you can see the beginnings of how a search function, something we all use every day in one form or another, works under the hood. I’m excited to find ways to put these to use in my future code.

Fun fact: just like queues and stacks, you can ‘add’, ‘peek’, or ‘remove’ from these data structures.

student of code. var my_homes = [‘NY’, ‘MTL’, ‘DC’, ‘EDI’, ‘FL’, ‘?’]