As I remember, a binary search tree is made up of nodes starting with a root node. A node usually consists of a value and two child nodes. Similar to a linked list, each node keeps a link to no more than two children.
- Run project and do a GET
- Review output
For this implementation, I tried to do it all from memory and I almost succeeded 🙂 This is what I came up with.
First, we build the tree. The first node will be null, so its value is seeded with the first value from the values array. Then, for each following value in our values array, we determine if it is greater or smaller than the current node value. If greater, we assign it to the right node. If less, to the left. Either route then calls buildTree(node) with the new sub-node as the root.
Once we are out of values, we traverse the tree to see the output.
I had a couple of issues:
- The recursive nature of trees made me stumble a bit until I figured out the basic flow.
- Additionally, I tried to use an abstract class for the tree node, but it didn’t turn out like I thought. So, to move forward, I just created an object for every node.
After that, it all made sense! Next post on this will be how to keep the binary search tree balanced while populating it.