Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. A single node tree is a BST Have you met this question in a real interview? Yes Example An example:

  2
 / \
1   4
   / \
  3   5

The above binary tree is serialized as {2,1,4,#,#,3,5} (in level order).

Solution: BST have the property that inorder is ascending order.

public boolean isValidBST(TreeNode root) {
     if(root == null) {
         return true;
     }
     Stack<TreeNode> stack = new Stack<TreeNode>();
     TreeNode p = root, prev = null;
     while(!stack.isEmpty() || p != null) {
         if(p != null) {
             stack.push(p);
             p = p.left;
         }
         else {
             TreeNode n = stack.pop();

             if(prev != null && n.val <= prev.val)
                 return false;

             prev = n;

             p = n.right;
         } 
     }
     return true;
}