Simple Recursive O(1) Memory


  • -2
    S

    Although this solution has a stack, the stack will always have only one item pointing to the previous node in ascending sequence.

    public bool IsValidBST(TreeNode root)
    {
        // use inorder traverse to put treenode to ascending order
        Stack<TreeNode> stack = new Stack<TreeNode>();
        return InorderBST(root, stack);
    }
    
    public bool InorderBST(TreeNode root, Stack<TreeNode> stack)
    {
    
        if (root == null)
            return true;
    
        if (root.left != null)
        {
            if (!InorderBST(root.left, stack)) return false;
        }
    
        // visit the node   
        if (stack.Count() > 0) // if there is item in stack
        {
            TreeNode node = stack.Pop();
            if (node.val >= root.val) return false;
        }
        stack.Push(root);
    
        if (root.right != null)
        {
            if (!InorderBST(root.right, stack)) return false;
        }
    
        return true;
    }
    

    If you are using C#, you can eliminate the need of stack by replacing with the ref treeNode to point to the previous.

    public bool IsValidBST(TreeNode root) {
        // use inorder traverse to put treenode to ascending order
        // ref value to point to previous
        TreeNode prev = null;
        return InorderBST(root, ref prev);
    }
    
     public bool InorderBST(TreeNode root, ref TreeNode prev) {        
        if(root == null) 
            return true;
        
        if(root.left != null)
        {
            if(!InorderBST(root.left, ref prev)) return false;
        }
        
        // visit the node   
        if(prev!= null)
        {
            if(prev.val>= root.val) return false;
        }
        prev=root;
        
        if(root.right != null){
            if(!InorderBST(root.right, ref prev)) return false;
        }
        
        return true;
    }

  • 1
    B

    This is not O(1) because the recursive runtime stack will take O(h) memory.


Log in to reply
 

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