Home
Teaching Kids Programming – Four Algorithms to Validate a Binary Search Tree
Tags:, , , , , , , ,

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

August 18, 2022 No Comments algorithms, python, Recursion, recursive, teaching kids programming, youtube video

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

validate-a-binary-search-tree Teaching Kids Programming - Four Algorithms to Validate a Binary Search Tree algorithms python Recursion recursive teaching kids programming youtube video

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:

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

# 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)
# 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. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 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
# 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 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
# 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.

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

# 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)    
# 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:

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

# 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
# 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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1091 words
Last Post: Teaching Kids Programming - Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree
Next Post: Teaching Kids Programming - Algorithms to Count Equal Row and Column Pairs in a Square Matrix using Hash Map

The Permanent URL is: Teaching Kids Programming – Four Algorithms to Validate a Binary Search Tree

Related posts:

  1. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  2. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  3. Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  4. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  5. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  6. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  7. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  8. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...

Leave a Reply