Overview

A Binary Search Tree (BST) is a unique form of a binary tree where each node follows a particular order: the left child contains nodes with values less than the parent node, and the right child contains nodes with values greater than the parent node. Verifying whether a given binary tree satisfies these conditions to qualify as a BST is a common problem in computer science.

This article delves into methods for determining if a binary tree is a BST, provides technical explanations, and discusses key considerations in evaluating a tree's properties.

Key Concepts

Binary Tree vs. Binary Search Tree

• Binary Tree: A tree data structure where each node has at most two children.
• Binary Search Tree (BST): A binary tree wherein:
  • All nodes in the left subtree have values less than the root's value.
  • All nodes in the right subtree have values greater than the root's value.
  • Both left and right subtrees are also BSTs.

Properties of a BST

• In-Order Traversal: The in-order traversal of a BST produces a sorted sequence of values.
• Unique Elements: Nodes in a BST have unique keys (no duplicate values).

Methods to Determine if a Binary Tree is a BST

Recursive Approach

To determine if a binary tree is a BST, the recursive approach verifies each node's value within a specific range. The process involves these steps:

1. Verify the Current Node: Ensure the current node's value falls between a defined minimum and maximum range.
2. Recur for Subtrees:
   • For the left subtree, update the maximum bound (now the current node’s value).
   • For the right subtree, update the minimum bound.

Algorithm

• Unique Values: A valid BST should not contain duplicate values.
• Edge Cases: A single node or an empty tree should return True as it fulfills the BST properties by default.
• Efficiency: The recursive approach uses $O(1)$ extra space but may reach a space complexity of $O(n)$ due to the recursive call stack. The in-order method operates iteratively with $O(n)$ time complexity.
• Morris Traversal: A space-efficient variation of in-order traversal that uses threading to keep space complexity $O(1)$.
• Augmented Tree: Utilize data structures with additional information that keeps track of subtree properties.