Validate a binary search tree in Java

Problem

In this problem, we want to validate if a binary tree is actually a binary search tree. As a reminder, a binary search tree has the property that, for every sub-tree, the value of the sub-tree root is greater that all values in the left child, and smaller than all values in the right child. Wikipedia has more on binary search trees.

Algorithm

Our strategy is to go through the tree using using in-order traversal (one of the depth-first search flavours). A valid binary search tree will only see increasing values when using that traversal. To verify this, we maintain the value of the last element seen in order to be able to compare it with the current element. This value is kept as an Integer instance variable that is easily accessed by the multiple recursive calls.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// Validate Binary Search Tree public class Solution { Integer previous = null; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } // Recursive call to the left child. if (!isValidBST(root.left)) { return false; } // In-order check that the current value is ordered. if (previous != null && previous => root.val) { return false; } // Update the previous value for the next checks. previous = root.val; // Recursive call to the right child. if (!isValidBST(root.right)) { return false; } return true; } }

This problem is a classic problem that notably appears on leetcode and career cup.