Teaching Kids Programming – Four Algorithms to Validate a Binary Search Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return whether it’s a binary search tree. A binary tree node is a binary search tree if :

All nodes on its left subtree are smaller than node.val
All nodes on its right subtree are bigger than node.val
All nodes hold the these properties.
Constraint
n ≤ 100,000 where n is the number of nodes in root

A Binary Search Tree (BST) is a Binary Tree with addition requirement that the nodes on the left tree are strictly smaller and the nodes on the right are strictly larger. “Strictly” means that there are no duplicate elements in the Binary Search Tree.

We can validate a binary search tree using two algorithms, which both has iterative and recursion implementations.

Recursive Algorithm to Validate a Binary Search Tree using Windows

At the begining, we set the window to (-inf, inf) for the node to be in, and we update/narrow the window as we traverse to the left, or to the right. The problem can be divided into two smaller sub problems which is to validate the left sub tree, and right sub tree recursively.

The Recursive version:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def f(root, minv, maxv):
            if not root:
                return True
            if root.val <= minv or root.val >= maxv:
                return False
            return f(root.left, minv, root.val) and f(root.right, root.val, maxv)
        
        return f(root, -inf, inf)

We use a stack to implement the non-recursion version aka the iterative algorithm. We need to push the node, and the current window for it to the stack so that we can validate.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:   
        if not root:
            return True
        
        stack = [(root, -inf, inf)]
        while stack:
            root, lower, upper = stack.pop()
            if root.val <= lower or root.val >= upper:
                return False
            if root.right:
                stack.append((root.right, root.val, upper))
            if root.left:
                stack.append((root.left, lower, root.val))
                
        return True

The order of the traversal does not matter here so we can use a queue aka deque (double ended queue) which in fact becomes a Breadth First Search:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:   
        if not root:
            return True
        
        q = deque([(root, -inf, inf)])
        while q:
            root, lower, upper = q.popleft()
            if root.val <= lower or root.val >= upper:
                return False
            if root.right:
                q.append((root.right, root.val, upper))
            if root.left:
                q.append((root.left, lower, root.val))
                
        return True

All the above algorithms to validate a binary search tree runs at O(N) time and O(N) space where N is the number of the nodes in the given binary (search) tree.

Recursive Algorithm to Validate a Binary Search Tree using Inorder Traversal

If we perform an inorder traversal algorithm, we should get a ordered list/sequence on a binary search tree. Thus, we remember/update the last visited node, and the current node should be strictly larger than it.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:   
        prev = -inf
        def dfs(root):
            nonlocal prev
            if not root:
                return True
            if not dfs(root.left):
                return False
            if root.val <= prev:
                return False
            prev = root.val
            return dfs(root.right)        
        return dfs(root)    

And, this can be implemented using the Stack/Iterative approach:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:   
        prev = -inf
        st = []
        while st or root:
            while root:
                st.append(root)
                root = root.left
            root = st.pop()
            if root.val <= prev:
                return False
            prev = root.val
            root = root.right            
        return True

So, same time/space complexity O(N). Which method do you favor best?

Algorithms to Validate a Binary Search Tree

• How to Validate Binary Search Tree in C/C++?
• Teaching Kids Programming – Recursive Algorithm to Validate a Binary Search Tree
• Teaching Kids Programming – Four Algorithms to Validate a Binary Search Tree

–EOF (The Ultimate Computing & Technology Blog) —