Validate Binary Search Tree

Patrick Leaton
Published: June 12, 2021, 2:18 p.m.
Problem Description

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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:

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

Example 2:

Input: root = [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.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1

 

The description was taken from https://leetcode.com/problems/validate-binary-search-tree/.

Problem Solution

#Recursive DFS
#O(N) Time, O(N) Space
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return False
 
        def dfs(node: TreeNode, low:int, high:int) -> bool:
            if not node:
                return True      
            if node.val <= low or node.val >= high:
                return False
            valid_left = dfs(node.left, low, node.val)
            valid_right = dfs(node.right, node.val, high)
            return valid_left and valid_right
       
        return dfs(root, -2**31-1, 2**31)
 
 
#Iterative DFS
#O(N) Time, O(N) Space
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return False
 
        def dfs(root: TreeNode, low:int, high:int) -> bool:
            stack = [(root, low, high)]
            while stack:
                node, low, high = stack.pop()
                if node.val <= low or node.val >= high:
                    return False
                if node.left:
                    stack.append((node.left, low, node.val))               
                if node.right:
                    stack.append((node.right, node.val, high))
            return True
 
        return dfs(root, -2**31-1, 2**31)

Problem Explanation

In a BST, each left subtree has to be less than the parent and each right subtree has to be greater.  There also can't be duplicate values.

While keeping those rules in mind, we can solve this problem by performing a Depth-First Search. 

The description also states that a node value can't be less than the lowest thirty-two-bit integer or greater than the greatest thirty-two-bit integer.

If we have traversed the tree with each of these requirements and constraints met, we have validated the tree.

Recursive DFS

The recursive solution for this problem is fairly short.

First off, if our root node value is null then it fails the given constraints so we will return false.

            if not root:
                return False

If that is not the case then let's start by building our dfs function which will require a node, a lower bound, and an upper bound for each function call.

        def dfs(node: TreeNode, low:int, high:int) -> bool:

 

Now let's set our base cases.

If we are at a null node, then that means we have exhausted the search of a subtree branch while every node we encountered followed the right requirements and constraints.  If that is the case, we will return true to let our parent function calls know that everything was good from here.

            if not node:
                return True

 

Next, if our node value is less than or equal to our lower bound, that can mean a few things:

  1. We have a duplicate value.
  2. We are in a left subtree and our value is outside the bounds of negative two to the thirty-first power, making it invalid.
  3. We are in a right subtree and have a right child node that is less than its parent.
  4. We are in a left subtree but were previously in a right subtree so the lower bound was overwritten by a right node's parent node, so even though we have a node that may be less than its parent, it may be greater than a previous root.  The entire left subtree of any given root needs to be less than the root.

If our node value is greater than or equal to our upper bound, that will break similar rules:

  1. We have a duplicate value.
  2. We are in a right subtree and our value is outside the bounds of two to the thirty-first power minus one, making it invalid.
  3. We are in a left subtree and have a left child node that is greater than its parent.
  4. We are in a right subtree but were previously in a left subtree so the upper bound was overwritten by a left node's parent node, so even though we have a node that may be greater than its parent, it may be less than a previous root.  The entire right subtree of any given root needs to be greater than the root

If any of those cases are true, this node we just encountered invalidated the subtree so we will return false.

            if node.val <= low or node.val >= high:
                return False

 

After we have checked this node against those two conditional base cases, we will check both children as well.

If we have a left child, it can't be lower than the lower bound and it can't be greater than the current node.

            valid_left = dfs(node.left, low, node.val)

 

If we have a right child, it can't be greater than the upper bound and it can't be less than the current node.

            valid_right = dfs(node.right, node.val, high)

 

We'll check if both of those conditions are true.

            return valid_left and valid_right

 

Now that our dfs function is built, all we need to do is make the initial call by passing one number lower than our node value's possible lower bounds, and one number higher than our node value's possible upper bounds.  We do this because we want these values to be overwritten later by values that are actually within the allowed bounds of a test case.  We could also choose to use negative infinity and infinity, but this is a slight optimization.

        return dfs(root, -2**31-1, 2**31)

 

If each function on the calls stack returns true, it means that the DFS traversed past the end of each branch and validated each subtree branch along the way.

Iterative DFS

The iterative version follows the same exact formula.

The only difference is we will be using a loop and a stack in place of a recursive call stack.

First off, if our root node value is null then it fails the given constraints so we will return false.

            if not root:
                return False

If it is not, then let's start by building our dfs function which will require a node, a lower bound, and an upper bound for the initial call.

        def dfs(root: TreeNode, low:int, high:int) -> bool:

 

Then, we will push those starting values given as the function argument into a stack.

            stack = [(root, low, high)]

 

Next, we will create a loop that will continue to run while the stack still has child nodes to process.

            while stack:

 

At the beginning of each iteration, we will pop a node, a lower bound, and an upper bound off of the stack.

                node, low, high = stack.pop()

 

Just to reiterate what was mentioned in the recursive version,  if our node value is less than or equal to our lower bound, that can mean a few things:

  1. We have a duplicate value.
  2. We are in a left subtree and our value is outside the bounds of negative two to the thirty-first power, making it invalid.
  3. We are in a right subtree and have a right child node that is less than its parent.
  4. We are in a left subtree but were previously in a right subtree so the lower bound was overwritten by a right node's parent node, so even though we have a node that may be less than its parent, it may be greater than a previous root.  The entire left subtree of any given root needs to be less than the root.

 

If our node value is greater than or equal to our upper bound, that will break similar rules:

  1. We have a duplicate value.
  2. We are in a right subtree and our value is outside the bounds of two to the thirty-first power minus one, making it invalid.
  3. We are in a left subtree and have a left child node that is greater than its parent.
  4. We are in a right subtree but were previously in a left subtree so the upper bound was overwritten by a left node's parent node, so even though we have a node that may be greater than its parent, it may be less than a previous root.  The entire right subtree of any given root needs to be greater than the root

If any of those cases are true, this node we just encountered invalidated the subtree so we will return false.

                if node.val <= low or node.val >= high:
                    return False

 

After we have checked the current node against that condition, we will check both children as well, if they exist.  If they do, we will push them onto the stack.

If we have a left child, it can't be lower than the lower bound and it can't be greater than the current node.  

                if node.left:
                    stack.append((node.left, low, node.val))    

 

If we have a right child, it can't be greater than the upper bound and it can't be less than the current node.

                if node.right:
                    stack.append((node.right, node.val, high))

 

If we have emptied the stack and broke from the loop then that means the DFS traversed to the end of each branch and validated each subtree branch along the way.

If that is the case, we will return true.

            return True

Same as in the recursive solution, now that our dfs function is built, all we need to do is make the initial call by passing one number lower than our node value's possible lower bounds, and one number higher than our node value's possible upper bounds.  We do this because we want these values to be overwritten later by values that are actually within the allowed bounds of a test case.  We could also choose to use negative infinity and infinity, but this is a slight optimization.

        return dfs(root, -2**31-1, 2**31)