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

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

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:

 ```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?

GD Star Rating