ProgramGuru.org

ProgramGuru.org

Check if a Binary Tree is a Binary Search Tree

Visualization

Algorithm Steps

  1. If the tree is empty, return true.
  2. For each node, check if its value is within the valid range (min and max).
  3. If the node's value does not satisfy min < node.val < max, return false.
  4. Recursively verify the left subtree with an updated upper bound (max = node.val) and the right subtree with an updated lower bound (min = node.val).
  5. If all nodes satisfy the BST property, return true.

Check if a Binary Tree is a Binary Search Tree - Code Examples Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isBST(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if not (min_val < root.val < max_val):
        return False
    return isBST(root.left, min_val, root.val) and isBST(root.right, root.val, max_val)

# Example usage:
if __name__ == '__main__':
    # Construct BST:      2
    #                   /   \
    #                  1     3
    root = TreeNode(2, TreeNode(1), TreeNode(3))
    print(isBST(root))