How to determine if a graph is a Binary Search Tree given the root node using Python

happytrees

I recently ran across a pretty cool challenge on Hacker rank: Cracking the coding interview series which you can find here: Is it a binary tree?

Flash back real quick to what a binary tree is.  It is a graph structure composed of notes that have a left child, a right child, and the data field.  Now throw in the search part of it where ever left child of a node is less then that node and every right child is greater then that node.  Seems easy enough.

Going on just that data one would think “Well just check those children against those rules and bam, you’re done!”. Also repeated data would mean it is an  invalid tree. We can track this using a dictionary to see, which is very similar to a hash table to do direct o(1) stores and look ups using the data as a key and a flag for the value.  Through recurssion and making this an optional param we can pass around this data structure during our traversal. Using that premise we end up with the following code assuming a preorder traversal which you can read about here.

This was almost a good attempt except it failed most of the tests.  I wasn’t sure the problem until I realized I was assuming we only needed to check the direct children for the rule and not all the children.  To put this into a visualization the tree below would pass the code above but is obviously not a valid tree because the leaf node in red is clearly bigger then the root node.

BadTree.png

Being able to debug that some of the test cases followed this structure was the significance of the pre-order traversal since the input would say 1,2,5,8,14 but it was not clear how these values were being inserted but I could use print statements on the custom input to see the actual structure of the tree by using standard print statements. One can only assume there is some random seed generation from the first input from the debug to form the tree that would give us this case.  That’s just under the covers stuff but either way this sucker was giving us problems. Now the next thought is “What is true about all children of nodes?”

Go ahead and take a few minutes to see if you can think through the solution before scrolling down more.

This is more just a variation of the main rule and that is that the values should fall within a range of values given the grand parent.  Also if we assume a child passes our rules that we can slide our range as our algorithm progresses due to the lovely old transitive property. It took me a couple more iterations to fully dominate the range tracking but this is the final working code that passed all the checks without needing extensive utility functions:

I hope this helps give more insight into the wonderful world of binary trees. If you liked this post please share it on your favorite social network and leave me a comment below.

Leave a Reply