Press "Enter" to skip to content

Check if a binary tree is a BST in Java

Ajk 0

This is a question that comes quite often as a preliminary / phone interview question. How do we check if a binary tree is a BST in Java? In other words we need to validate if a binary tree is a binary search tree.

As for our previous topic for checking whether a tree is balanced, the first step is to properly define the problem. So let us define what does it mean for a binary tree to be a BST.

Check if a binary tree is a BST in Java – Definition

As This Excellent Article defines:

Binary Search tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x.

Given this definition we can try to visualize it. Note that not only the current node needs to be bigger than the its left child. It needs to be bigger than the whole left subtree. The same goes for the right child. After careful evaluation of the definition we should come up with something like this to visualize a binary tree that is a BST.

Check if a binary tree is a BST in Java
Binary Search Tree

Hence we completed the first step by having a definition and a visualization for our problem. Now all we have to do is methodically devise a step by step algorithm to validate that a binary tree is indeed a BST.

Check if a binary tree is a BST in Java – Algorithm Idea

For each node in the tree the following must be true in order for it to be a binary search tree:

  1. The left sub-tree of a node contains only nodes with values less than the node’s value.
  2. The right sub-tree of a node contains only nodes with values greater than the node’s value.

Note that by the definition and algorithm idea above, a null pointer would be considered as a BST, since it does not break the validation. Since we are checking each sub-tree in the tree, this can be easily be implemented as a recursive call.

Check if a binary tree is a BST in Java – Recursive Algorithm – Bottom Up

  1. Check if left sub-tree is a BST. Get the max value of the left subtree.
  2. Check if right sub-tree is a BST. Get the min value of the right subtree.
  3. Validate that the current node’s value is bigger than the max value of the left subtree and smaller than the min value of the right subtree.

If you rationalized everything as I did until now, the above algorithm should come naturally. You need to know min and max and validate that our node’s value is in the middle. If all nodes have this property then we have validated that our binary tree is a BST. We will see in a second how putting this to code will not be as trivial as we would think.

Check if a binary tree is a BST in Java – Recursive Implementation – Bottom Up

That was a bit harder to write than expected, was it not? One of the main problems that come up in the heat of the interview is trying to pass 2 or more variables up to a recursive call. This problem can easily be solved by creating a placeholder class specific to your use case. In fact the above example does exactly that to check if a binary tree is a BST. So keep that in mind for the next time you get stuck at trying to bubble up two or more variables in a tree.

The other way to go around the problem and probably devise a cleaner solution, would be modify the algorithm to validate top-to-bottom instead of bottom up. Meaning we pass our constraints from the top node to the bottom and validate that each node does not cross it’s left and right ancestors min and max. Since we can pass as many arguments as we want to a recursive function, this will be a lot easier to do. Note that this is another way you can re-frame recursive problems!

Check if a binary tree is a BST in Java – Recursive Algorithm – Top to bottom

  1. Check if left sub-tree is a BST. All nodes values must have an upper bound equal to the current node’s value.
  2. Check if right sub-tree is a BST. All nodes values must be bigger than the current.

Seems easy enough? After we have clearly specified the algorithm all that is left to do is to put it in code. Given that we have already thought out how it would pan out, it should turn out a lot simpler than our previous attempt.

Check if a binary tree is a BST in Java – Recursive Implementation – Top to bottom

Since it passes constraints from the top to the bottom, the solution above is called a top to bottom approach, while our first approach is commonly called a bottom-up approach.

Now what if your interviewer asks you to come up with yet another algorithm? Digging through your knowledge, you will remember that there are different type of traversals for tree. In fact we have already tried to solve for a rather uncommon Zig-Zag Tree Traversal. However some of the most common ones that one should study, are In-Order, Pre-Order and Post-Order Traversal.

Check out this article to see when to use which and get some idea on how you can get help from each of these algorithms. As you will be able to see, doing an In-Order-Traversal mimics you go from the far left to the far right of the tree, touching nodes one by one. In fact you can envision a vertical line going through the tree from left to right. For our current problem, that means that it will also touch nodes progressively with higher value. It turns out we can use this simple fact to check if a binary tree is a BST.

Check if a binary tree is a BST in Java – In-Order-Traversal Algorithm

  1. Traverse nodes of the tree inorder.
  2. Keep make sure every next node value is bigger than the previous one.

Since we did most of our explanation before devising the algorithm, it should be fairly straight forward to put it to code.

Check if a binary tree is a BST in Java – In-Order-Traversal Implementation

We just came up with our third solution to this problem in less than 15 minutes! Pretty great isn’t it! I am sure any interviewer would be impressed with all this and would mark this as a pass to his question.

Last but not least, we can quickly observer that for each of our algorithms we touch each node once and we keep no auxiliary data structures. Hence our Time Complexity is going to be O(n) and our Space Complexity is going to be O(1). If this was obvious to you than you are well on the path to become an algorithm guru!

As always feel free to ask questions or post any feedback!
Hope you guys enjoyed it! And I’ll see you guys next time ;D.

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *