Leetcode - find if BST is valid or not

Question

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.

Example 1:

  2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

 5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

My solution

1. Do inorder traversal and keep it in stack.
2. Iterate through stack to see if any of the value on top is less than equal to second top.

Definition for a binary tree node.

 public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
  }




class Solution {

    public void doInOrderTraversal(TreeNode root, Stack s) {
        if(root == null) {
            return;
        }
        doInOrderTraversal(root.left, s);
        s.push(root.val);
        doInOrderTraversal(root.right, s);

    }

    public boolean isValidBST(TreeNode root) {

        if(root == null) {
            return true;
        }

        Stack<Integer> stack = new Stack<>();

        doInOrderTraversal(root, stack);

        while(!stack.isEmpty()) {
            int top = stack.pop();
            if(stack.isEmpty()) {
                return true;
            }
            int secondTop = stack.peek();
            if(top <= secondTop) {
                return false;
            }
        }
        return true;
    }
}

I was thinking to not use stack, but two values current and previous. And keep check if current is less than previous then only break. I am not sure, how to do this. Please suggest.

Answer 1

Your solution:

seems legit :) One thing I'd suggest here is to use ArrayDeque instead of Stack

Another possible solution:

Basically, for every subtree we have constrain, that every node in it should be in range (X, Y).

For root this range will be (-inf; +inf) - in other words, there could be any value in root.

For root's left subtree range will be (-inf, value-in-root), for right - (value-in-root, +inf).

Last thing - on each iteration we should check, that value in node is within this range, like so:

public boolean doInOrderTraversal(TreeNode root, int min, int max) {
    if (root == null) {
        return true;
    }
    if (root.val <= min || root.val >= max) {
        return false;
    }

    return doInOrderTraversal(root.left, min, root.val) && doInOrderTraversal(root.right, root.val, max);
}

Answer 2

Your code is correct and IMHO optimal for the algorithm it implements.
The only two details I would recommend to change are:

• rename the node member val to value – there's no reason to strip the last two characters,
• and make the doInOrderTraversal method private – it seems useful inside this Solution only.

What concerns the algorithm: yes, you can reach the same result without the additional Stack object. Here is an example of a full recursive test without an explicit stack.

The base case is an empty tree, which is a valid BST.

A left subtree of any node has values bounded from above by that node, similarly a right subtree values are bounded from below. It follows that any subtree is bounded by its closest left- and right-side ancestors (except the left-most branch, which has no left-side ancestor, and the right-most branch, which has no right-side ancestor; and a special case of the root node, which has no ancestor at all).

(Using your TreeNode class.)

class Solution {
    
    public boolean isValidBST(TreeNode root) {
        return isValidBST(null, root, null);
    }

    private boolean isValidBST(TreeNode leftAncestor, TreeNode node, TreeNode rightAncestor) {
        // base case
        if (node == null)
            return true;

        // bounds by ancestors (duplicated keys not allowed; replace
        // <= and >= with < and >, respectvely, to allow duplicates)
        if (leftAncestor != null && node.val <= leftAncestor.val)
            return false;

        if (rightAncestor != null && node.val >= rightAncestor.val)
            return false;

        // this node valid - validate its subtrees; this node becomes
        // the closest right-side ancestor for its left subtree
        // and the closest left-side ancestor for its right subtree
        return
            isValidBST(leftAncestor, node.left, node) &&
            isValidBST(node, node.right, rightAncestor);
    }
}

At the cost of additional conditions (which obfuscate the code a bit) you can save about a half of recursive calls:

    public boolean isValidBST(TreeNode root) {
        return (root == null) || isValidBST(null, root, null);
    }

    private boolean isValidBST(TreeNode leftAncestor, TreeNode node, TreeNode rightAncestor) {
        assert node != null;

        // bounds by ancestors (duplicated keys not allowed; replace
        // <= and >= with < and >, respectvely, to allow duplicates)
        if (leftAncestor != null && node.val <= leftAncestor.val)
            return false;

        if (rightAncestor != null && node.val >= rightAncestor.val)
            return false;

        // this node valid - validate its subtrees; this node becomes
        // the closest right-side ancestor for its left subtree
        // and the closest left-side ancestor for its right subtree
        return
            (node.left == null || isValidBST(leftAncestor, node.left, node)) &&
            (node.right == null || isValidBST(node, node.right, rightAncestor));
    }

---

If you're allowed to modify the tree...

...you can also get rid of the stack by transforming your tree into a list – it's the first phase of the Day-Stout-Warren algorithm to balance a BST.

The algorithm is a constant-memory – it does not use a stack, it just iterates through the right-most branch of the tree while merging left subtrees into it.

Then you can iterate through the list to check if values make a strictly increasing sequence.

---

Of course you can make the final testing inside the tree-to-list transformation. That would save you one loop in the code structure, but it would also make the code much less readable with virtually no gain in efficiency.

---

I wonder, however, what do these notes mean:

Input: [2,1,3]
Input: [5,1,4,null,null,3,6]

Are the code expected to read and parse the character line shown?
Or is it fed with an array?
In the latter case, does it mean it's array of Integers?
If it is supposed to be array of ints, what does null represent?