Binary Search Trees can be our friends

Confession: I only met my first Binary Search Tree a week ago. But now I’d like to say that we’re buddies, and I’d like to help you be friends with Binary Search Trees too!

As I’ve started preparing for software engineering interviews, I decided to attend my first whiteboarding algorithms Meetup with Women Who Code last week. All was going well, until we came upon a Binary Search Tree problem — I had never seen one before! I was, to say, completely stumped (hey-o!) As others started tackling the problem, I asked myself: “Umm…what even is a binary search tree? Let alone, a plain old binary tree? How do we decide between depth-first or breadth-first search? What’s all this talk about .left and .right, and how did we get access to those? How do we translate an array of values into a BST?”

If you’ve panicked to yourself about these questions too, take a deep breath and know that it’s all going to be okay. I spent the last week climbing all over binary trees and diving deep into recursion, and I’m happy to say that at a whiteboarding Javascript Coders Meetup yesterday (just one week after I didn’t even know what a BST was), I was able to solve a BST problem and help others follow my solution! It inspired me how much a brain can learn in only one week — I went from literally crying after seeing my first BST to now finding these problems to actually be FUN. I welcome you to hop on the binary search trees train too! In this post I’ll share my newfound understanding of them, then in the next post I’ll show you how to solve LeetCode’s “Convert Sorted Array to Binary Search Tree” problem with Javascript!

First things first: let’s understand the basics of binary trees.

❓What the heck is a binary tree? | ✔ It’s a data structure that looks like an upside-down tree, where each point (a.k.a. node) can branch down to have at most two children (one to the left and one to the right).

❓What are root nodes and leaf nodes? | ✔ The root node is the node at the very top of the tree. Any given tree can only have one root node, meaning that the root cannot be the child of another node. Leaf nodes are nodes at the very bottom of the tree, meaning that they have no children.

❓What is the “height” of a tree? | ✔ The height of a tree is the length of its longest branch, or the number of edges from the root node to the furthest leaf node.

❓Do binary trees come pre-built into Javascript? | ✔ Binary trees are not pre-built into Javascript, but you can write a function to represent nodes as objects. Each node object will have a property called .val or .value (whatever you prefer), to represent the node’s value. Each node will also have properties .left and .right that point to its children. So if you have the root node, you have access to the entire tree.

❓How do I represent the lack of a node? | ✔ Just represent this empty space in the tree with null (instead of a node object). So for a node that has no children (such as a leaf node at the bottom of the tree),.left and .right are both null .

Now let’s understand the basics of binary SEARCH trees.

❓What makes a binary tree a binary SEARCH tree? | ✔ A binary search tree is a special kind of binary tree — it has all the same rules as a regular binary tree, but it also requires that any left child’s value must be less than the parent’s value, and the right child’s value must be greater than the parent’s value.

❓What makes binary SEARCH trees so useful? | ✔ If we zoom out and look at the tree in its entirety, the entire left subtree’s values will all be less than the root’s value, and the entire right subtree’s values will all be greater than the root’s value. Thus, BSTs provide improved time complexity, which is a fancy way of saying we can find things faster. If we are looking for a specific value somewhere among the nodes, we can cut our search in half at each step. Why? Since our values are sorted, if the root value is greater than our target, we only have to check the left side of the tree! If it’s less than our target, we only have to check the right side! This magic happens at every step. (For you fancy folk, this gives us O(log n) time complexity).

❓How do we traverse (a.k.a. travel through all the nodes of) a tree? | ✔ We have two options: breadth-first vs. depth-first. Without getting too “deep”, this basically means we can either go wide first, or go long. Breadth-first means you check every node at each level before moving on to the next (lower) level. Depth-first means you first aim to go all the way down a branch to the very end until you reach a leaf.

Takeaways:

Phew, we learned a lot! But don’t you feel a little more comfortable with binary search trees now? Now that we know BSTs well enough to count them among our friends, it’s time to play with them in an actual problem-solving setting. In the next post, let’s learn how to solve LeetCode’s “Convert Sorted Array to Binary Search Tree” problem with Javascript.

Props to:

Leaf It Up To Binary Trees, Vaidehi Joshi

Implementation of Binary Search Tree in Javascript, Geeks for Geeks

Tree (data structure), Wikipedia

Women Who Code NYC Meetup

Javascript Coders Meetup