JavaScript – Binary Search Tree – Populate

GitHub Hub Code

While reviewing patterns I have implemented before in C#, I bumped into a binary search tree, so I thought I would create a JavaScript version 🙂

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.

To view:

  • Run project and do a GET

Screen Shot 2017-03-26 at 8.51.53 PM

  • Review output

Screen Shot 2017-03-26 at 8.34.56 PM

For this implementation, I tried to do it all from memory and I almost succeeded 🙂   This is what I came up with.

Screen Shot 2017-03-26 at 8.35.40 PM

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.

Screen Shot 2017-03-26 at 9.17.12 PM

Once we are out of values, we traverse the tree to see the output.

Screen Shot 2017-03-26 at 9.17.25 PM

I had a couple of issues:

  • My output came out backwards. So I wrote out by hand my input values and laid out what the tree would roughly look like (not well ordered as I will do this in my next post (ish)). Turns out I had forgotten that arrays in JavaScript are stacks (i.e. First In First Out (FIFO)).

Screen Shot 2017-03-26 at 9.04.26 PM

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

Stay tuned!

References

  1. http://stackoverflow.com/questions/23856618/finding-the-parent-of-a-node-in-a-binary-tree

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s