LeetCode Validate Binary Search Tree: Bottom Up, Top Down and Inorder

Overview

There are 3 linear time solutions to LeetCode Validate Binary Search Tree: 1) Bottom Up to find min/max; 2) Top Down to put upper/lower constraints; 3) Inorder

LeetCode Validate Binary Search Tree: Bottom Up

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.

Solution: Bottom Up, Top Down and Inorder

We analyze this problem step by step:

(1) First wrong attempting: By the definition of BST above, it is easy for people to directly follow this description and do the validation recursively. That is, DFS the tree and check each node, whether the left child is less than the current node, and the right child is larger than the current node. If this is true, then return DFS_IS_BST(Left Child)  && DFS_IS_BST(Right Child). This is a simple one pass through the tree in O(N) time, but this is incorrect, the following is a counter example: for each node, we have the fact that for the node, it has a smaller left child, and a larger right child, and the left subtree and the right subtree are also BST, however, the whole tree rooted at 3 obviously is not BST. This is because we never check the relative order between nodes across more than 1 levels. We will discuss approaches to correct this.

3
     /   \
    2     7
   / \  
  1   4

(2) Correct but inefficient method: By definition, a BST requires all the nodes in the left subtree is less than the root node while all the nodes in the right subtree is larger than the root node. Then ok, we do two nested DFS, the outer DFS is responsible to traverse the nodes in the tree, to check the current node we reach in this outer DFS, we use an inner DFS to check the left subtree of this current node to check whether EVERY node in the left subtree is less than the current node, and similarly we need to check the right subtree. So for every node we need a DFS to traverse the subtrees of the node to do the checking. The total time comlexity would be O(N^2).

(3) Correct and linear time appraoch 1 (bottom up): Let’s think about approach (2) a bit further, is there any repeated computation we could save? The answer is yes. The idea is that to make sure all the nodes in the left subtree is less than the root node, we only need to know the maximum value of among the nodes of the left subtree, and to check the right subtree, we need to know the minimum value of the right subtree.

So here is the approach, for each node in the tree we calculate the minimum AND maximum value of the subtree rooted at this node. We could just use a single DFS to get this results for all the nodes (why? think about it, this is where the bottom up term shows up). Then we can perform another DFS to check each node, whether the property of a BST is preserved or not by the criteria previously metioned. Or one can combine the check and calculation of the minimum and maximum value together.

The following code implements this bottom up idea and is accepted by the LeetCode OJ to pass this  Validate Binary Search Tree problem:

class Solution {

    public:
        bool dfs(TreeNode *root, int *minr, int *maxr) {
            if (NULL == root)
                return true;
            if (NULL == root->left && NULL == root->right) {
                *minr = root->val;
                *maxr = root->val;
                return true;
            }

            int minvl = INT_MIN, maxvl = INT_MAX;
            int minvr = INT_MIN, maxvr = INT_MAX;
            bool ret = dfs(root->left, &minvl, &maxvl) && dfs(root->right, &minvr, &maxvr);

            if (root->left && !root->right) {
                ret = ret && (root->val > maxvl);
                *minr = min(root->val, minvl);
                *maxr = max(root->val, maxvl);
            }
            if (root->right && !root->left) {
                ret = ret && (root->val < minvr);
                *minr = min(root->val, minvr);
                *maxr = max(root->val, maxvr);
            }
            if (root->left && root->right) {
                ret = ret && (root->val > maxvl) && (root->val < minvr);
                *minr = min(root->val, min(minvl, minvr));
                *maxr = max(root->val, max(maxvl, maxvr));
            }

            return ret;
        }

        bool isValidBST(TreeNode *root) {
            int minv = INT_MIN, maxv = INT_MAX;
            return dfs(root, &minv, &maxv);
        }

};

(4) Correct and linear time appraoch 2 (top down) : Similar to (3) but we try to think about the property of BST in a different angle. For a BST, each node, cannot be too larger nor too small, the ancestors put the minimum and maximum bound on the children nodes (top down thinking). So for root node, there is no constraint (INT_MIN, INT_MAX), but for the left child of the root, there is a upper bound by root->val, and for the right child there is a minimum bound for it by root->val. Recursively put this bound on each node, and a simple DFS could finish all the checking, if there is any node which is not in the given bound constraint, we directly return false. The following code implements this bottom up idea and is accepted by the LeetCode OJ to pass this  Validate Binary Search Tree problem:

bool dfs(TreeNode *root, int upper, bool upperBounded, int lower, bool lowerBounded) {
    if (NULL == root)
        return true;
    if ((upperBounded && root->val >= upper) || (lowerBounded && root->val <= lower))
        return false;

    return dfs(root->left, root->val, true, lower, lowerBounded)
        && dfs(root->right, upper, upperBounded, root->val, true);
}

bool isValidBST(TreeNode *root) {
    return dfs(root, 0, false, 0, false);
}

Remarks:

  1. The code is more compact than the bottom up approach
  2. Note we cannot use INT_MAX or INT_MIN to bound and test the node value constraint because the value itself could be INT_MAX/INT_MIN, for cases where the upper/lower bound are actually unbounded, it is incorrect to compare the node value with a limited value like INT_MAX vs INT_MAX, for example, when there is only a root node of value INT_MAX, actually this root node is not bounded at all by any number, so it would be wrong if we compare it with INT_MAX/INT_MIN.

(5) Correct and linear time appraoch 3 (inorder traveral) : This is quite a different angle, it is not hard to image that, if it is a BST, then then inorder traversal of the tree should issue an strictly increasing sequence, then just do an inorder traversal and verify if it is an increasing sequence and then it is done. Quite simple and neat here. The following is the source code which can pass the leetcode OJ:

class Solution {
public:
        int iPreviousValue;
	bool bFlagInit;
	bool isValidBST(TreeNode *root) {
            iPreviousValue = 0;
            bFlagInit = false;
            return isValidBSTInner(root);
	}
	bool isValidBSTInner(TreeNode *root) {
		if(NULL == root)
			return true;
		if(!isValidBSTInner(root->left))
			return false;
		if(!bFlagInit) {
			iPreviousValue = root->val;
			bFlagInit = true;
		}
		else {
			if(iPreviousValue >= root->val)
				return false;
			iPreviousValue = root->val;
		}
		if(!isValidBSTInner(root->right))
			return false;
		return true;
	}
};

Another good further reference you can check:

Check this reference out: “A program to check if a binary tree is BST or not

Summary

There are 3 linear time solutions to LeetCode Validate Binary Search Tree: 1) Bottom Up to find min/max; 2) Top Down to put upper/lower constraints; 3) Inorder

Written on May 9, 2013