Java Recursive | Using Pre-Order Traversal


  • 0
    M

    Create a list of preorder traversal and check if the list is sorted.

    Runtime - O(n)
    Space : O(n)

    Otherwise use recursion
    Idea is to do a preorder traversal of BST and keep on checking
    left > root > right

    So store the first leftmost val in a variable prev_val and when it recurs back to the parent of prev_val,
    check if prev_val > parent.val. If yes, return false. Otherwise, assign prev_val to parent.val and now go towards right.

       Integer prev_val;
        
        public boolean isValidBST(TreeNode root) {
            
            if (root == null) {
                return true;
            }
            
            if (!isValidBST(root.left)) {
                return false;
            }
            
            if (prev_val != null && prev_val >= root.val) {
                return false;
            }
            
            prev_val = root.val;
            
            if (!isValidBST(root.right)) {
                return false;
            }
            
            return true;
        }
    

Log in to reply
 

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