Teaching Kids Programming – Recursive Algorithm to Validate a Binary Search Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Binary Tree, our task is to validate if it is a binary search tree. In a BST (Binary Search Tree), all the nodes on the left sub-tree are strictly smaller than the parent node, and all the node in the right sub tree are larger than the parent node.

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

Recursive Algorithm to Validate a Binary Search Tree

We can pass a window of lower and upper bounds into the recursive function that will check the nodes in the current sub-tree to see if the nodes fall within the range. When we go to the left sub-tree, we update the upperbound of the window, similarly when we visit the right subtree, we update the lowerbound of the ranges.

At any time, if a node falls outside its current window, we immediately invalidate the result as not being a valid Binary Search Tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def checkBST(self, root, minv = -float("inf"), maxv = float("inf")):
        if root is None:
            return True
        if root.val < minv or root.val > maxv:
            return False
        return self.checkBST(root.left, minv, root.val) and \
                self.checkBST(root.right, root.val, maxv)
        
    def solve(self, root):
        return self.checkBST(root)

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def checkBST(self, root, minv = -float("inf"), maxv = float("inf")):
        if root is None:
            return True
        if root.val < minv or root.val > maxv:
            return False
        return self.checkBST(root.left, minv, root.val) and \
                self.checkBST(root.right, root.val, maxv)
        
    def solve(self, root):
        return self.checkBST(root)

As each node has to be checked exactly once, the time complexity is O(N). The space complexity is O(N) as we are using Recursion (which implicitly has caller stacks).

The BST definition is recursive: A valid BST’s left sub trees are all valid BSTs and so are its right sub trees. Therefore, we can solve this problem using Recursive algorithm.

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) —