Solving this problem in 3 different ways in Java


  • 0
    L

    Way#1: This approach relies on the inorder traversal of the tree. Remember that the inorder traversal will always maintain the ascending order and we could just verify it. We don't want to store this into a new array to add another space complexity. We must do it while recursing through the tree. The only caveat is that it will recurse all the way down to the leftmost even though the bst property may be violated in the earlier levels. We will better this by 3rd solution.

    public class Solution {
        private TreeNode prev;
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
              return true;
            }
            if (!isValidBST(root.left)) {
              return false;
            }
            if (prev != null) {
              if (prev.val >= root.val) {
                return false;
              }
            }
            prev = root;
            return isValidBST(root.right);        
        }
    }
    

    Way#2: This is a standard solution of using recursion and defining a lower and upper bound.

    public boolean isValidBST(TreeNode root) {
            return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
        }
        private boolean helper(TreeNode root, long lower, long higher) {
            if(root==null) {
                return true;
            }
            if(!(root.val>lower && root.val<higher)) {
                return false;
            }
            
            return helper(root.left,lower,root.val) && helper(root.right,root.val,higher);
        }
    

    Way#3: A non-iterative way using a queue to do level-order traversal using the lower and upper bound

    public boolean isValidBST(TreeNode root) {
            if(root==null) {
                return true;
            }
            
            Queue<Wrapper> queue = new LinkedList<>();
            queue.add(new Wrapper(root,Long.MIN_VALUE,Long.MAX_VALUE));
            while(!queue.isEmpty()) {
                Wrapper obj = queue.poll();
                TreeNode node = obj.node;
                if(!(node.val>obj.lower && node.val<obj.higher)) {
                    return false;
                }
                if(node.left!=null) {
                    queue.add(new Wrapper(node.left,obj.lower,node.val));
                }
                if(node.right!=null) {
                    queue.add(new Wrapper(node.right,node.val,obj.higher));
                }
            }
            return true;
        }
        private class Wrapper {
            TreeNode node;
            long lower;
            long higher;
            Wrapper(TreeNode node, long lower, long higher) {
                this.node = node;
                this.lower = lower;
                this.higher = higher;
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.