Binary Search Trees and Recursion
In this post, I’m going to explain the basics of binary search trees, and in the process demystify one of the most mind-bending but super useful concepts in the developer’s toolkit: recursion.
A binary search tree is a special data structure defined by a few simple rules that result in some very useful and efficient functionality. But before we start to get into trees, we have to understand what they’re made up of — nodes.
What’s in a node?
A node is simply a small object that has a value — like a number — and points to one or more other nodes.
You can think of this like a scavenger hunt — each time you reach a node, you can access its value, and it also gives you a clue pointing to the location of the next node. In this way, you can move along the chain until you reach the final node (which points to a null value instead of another node).
These types of structures can be very efficient, but are also precarious — just like a scavenger hunt, if you lose the clue to the next node, you can never find it again!
Binary Search Trees:
Now we can move on to trees, which are just one of many ways to organize nodes. A tree is kind of like the organizational chart of a company. At the top is the boss (in the case of a tree this is the “root”). The boss has a number of people below them, and each of those people in turn has a number of people below them. At the very bottom level you have the unpaid interns (or in the case of the tree, the “leaves”).
A binary search tree is a specific kind of tree with two major characteristics.
- Each node has at most TWO children — a left child and a right child. (This is why it’s called “binary.”)
- The left child (and all of its children) must be less than or equal to the parent. (Remember “Left is Less.”)
- And the right child (and all of its children) must be greater than the parent.
What’s the alternative?
The binary search tree structure makes it extremely efficient to search through the tree and find, insert, or delete specific nodes. Let’s compare this with an unsorted tree — imagine, for example, we’re trying to find a node with value 6 in the tree pictured below.
Since the tree is not ordered in any way, we might need to search one by one through every node before we find it. That would be very inefficient! Now let’s look at how we’d approach the same search on a binary search tree.
We can start our search at the root. Since our target value (5) is less than the root value (10) and since we know that EVERYTHING to the right of the root is greater than 10, we can instantly eliminate that entire half the tree from our search! Next, we can move down a step to the root’s left child (5) and run the same check. This time, our target is greater than the node we’re checking, so we can eliminate everything to left. And so on, until we either find the target value, or reach one of the leaves, at which point, we can conclude our target value is not in the tree.
This provides an extremely intuitive and efficient search algorithm. But how do we implement this in code? One way is through a deceptively simple process called recursion, which can feel like a bit of a brain teaser but is actually a very important computer science concept to be familiar with!
So what is recursion?
In simple terms, recursion describes a function that calls itself. Let’s start with a simple example. Imagine you’re sitting in the back of a school bus, and all the way at the front is your friend Dave.
You want to see if Dave is free to read up about search trees after school, so you write a note that says:
Study binary search trees after school?
[ ] True [ ] False
You fold it up, and write Dave’s name on the front. Then you pass it to the person in front of you and wait for it to come back with an answer. They look at the front and see it’s not addressed to them, so they pass it to the person in front of them and wait for it to come back to them. Finally, the note reaches Dave. He sees it’s addressed to him, opens it up, writes his answer (true), and then passes it back to the person who gave it to him. They in turn pass it back to the person who gave it to them. And so on, until finally it gets back to you with a returned value, completing the process.
This is in essence a recursive process.
You can imagine a function called passNote that you first invoke in the back of the bus. Each person who receives the note checks to see if it’s for them, and if not, they in turn activate the exact same process. For this function to be successful, though, it’s critical that it has a stopping condition.
In this case, if the recipient of the note is the person it’s addressed to, they don’t pass it forward, but instead answer the question and send it back up the chain. On the other hand, if the person is the very last person in the row, and there’s no one left to pass it to, they send it back empty (indicating Dave has not been found). In the language of recursive function, these are called a “base case,” and without them the function could continue running itself forever.
Now, back to the binary search tree.
While it is equally possible to search through a binary tree using either recursion or iteration, the shape of a tree makes it a perfect candidate for recursion. The reason is that if you take any node of the tree, it actually serves as the root of its own mini tree, which follows the EXACT same rules as the original tree. Therefore, the very same function could be run starting on any node of the tree and it would search everything below that node.
So how does this work in practice? Let’s set up a basic function to search through a binary tree for a specific target value. We’ll want to pass into the function the starting node and the target value.
The base case:
The first step for any recursive function is to identify the base case or cases — the conditions under which the function returns a concrete result instead of calling itself again. In this case, we have two base cases:
- The node equals our target value–so we return true. This is the equivalent of our school bus note reaching the person whose name is on the front — they don’t pass it forward, they send it back with a value.
- The node has no children–so we return false. This is like the note reaching the front of the bus without finding the recipient. There’s no one left to pass the note to, so they send it back empty, and it can be concluded the recipient was not on the bus. (We’ll address how to implement this in code as the last step.)
The recursive case:
If the root doesn’t equal the target, we need to continue on down the tree. Since each node is the root of its own tree, you can see that our original root leads to two separate trees, a left tree and a right tree. If the target value is less than or equal to our root value, we know it must lie in the left tree, and if it’s greater, it must lie in the right tree.
Once we identify the correct tree to search, we simply run this very same function on that tree and return the result we get back! If the root equals the value we’re looking for, the function will return true. If not, it will continue the search using its two children and return that result.
Adding the finishing touches:
Now we can deal with that second base case, in which we get all the way down to the end of the line and still haven’t found the target value. In this case, we reach a node with a null value in the node.left or node.right position that we’d like to search next. An easy way to deal with this is to have the function return false if it’s run on a null node, which will be triggered when our final node tries to search its non-existent child node.
And that’s it!
If your head hurts already, don’t worry. Recursion is a notoriously slippery and confusing concept to wrap your mind around. But hopefully this has made it a little bit easier to understand both binary trees, recursion, and why they’re such a good match.
