Recursion || Iterative Inorder Traversal

  • 0

    Validate Binary Search Tree

    • Recursion Method

    Tree is defined recursively. So whenever we want to solve a problem related to Tree data structure, we'd better think about Recursion first.

    For a node in BST, it has two limitations MIN, MAX (MAX - its right node's value, MIN - its left node's value ).
    For a layer of definition (node.left, node, node.right), node.left's MAX is root.val, node.right's MIN is root.val.

    Thus, the recursion method is :
    private boolean isValid(TreeNode root, long min, long max) {};

        public boolean isValidBST(TreeNode root) {  
            return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
        private boolean isValid(TreeNode root, long min, long max) {
            if (root == null) return true;
            if (root.val <= min || root.val >= max) return false;
            return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    • Iterative Inorder Traversal Method

    Iterative Inorder Traversal can solve many problems about Tree. In this case, if we traverse the tree in-order, there should be an increasing sequence.

    We set a pointer PRE to represent the previous node, and the CURRENT node should be the one we pop from the stack. PRE should always smaller than CURRENT.

        public boolean isValidBST(TreeNode root) {
            if(root == null) return true;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode pre = null;
            while(root != null || !stack.empty()){
                while(root != null){
                    root = root.left;
                root = stack.pop();
                if (pre != null && pre.val >= root.val) return false;
                pre = root;
                root = root.right;     
            return true;

Log in to reply

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