Check if a Binary Tree is a Binary Search Tree - Visualization

Binary Search Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given the root node of a binary tree, determine whether it satisfies the properties of a Binary Search Tree (BST).

  • In a BST, for every node:
    • All nodes in its left subtree have values less than the node's value.
    • All nodes in its right subtree have values greater than the node's value.
  • Additionally, both the left and right subtrees must also be binary search trees.

Examples❯

Input Tree Is BST? Description
[10, 5, 15, 2, 7, 12, 20]
true All nodes satisfy BST properties: left subtree < root < right subtree at every node.
[10, 5, 8]
false Right child 8 of root 10 violates BST rule since 8 < 10.
[5]
true Single node is a valid BST by definition.
[] true An empty tree is considered a valid BST.
[10, 5, 15, 1, 12, 6, 20]
false Node 12 in left subtree of 15 violates BST rule since it's less than 15 but appears in right subtree.
[8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
true All left & right subtrees maintain valid ranges. This is a classic valid BST example.

Solution❯

Understanding the Problem

We are given a binary tree, and our task is to determine whether it satisfies the properties of a Binary Search Tree (BST). In a BST, for every node:

  • All nodes in its left subtree must contain values strictly less than the node’s value.
  • All nodes in its right subtree must contain values strictly greater than the node’s value.

This rule must be true not just at the root but recursively for all subtrees.

Step-by-Step Solution with Example

Step 1: Recognize the base case

If the tree is empty (i.e., the root node is null), it is considered a valid BST by definition because there are no violations possible.

Step 2: Use recursion with value boundaries

For each node, we must verify that its value lies within a valid range. Initially, the root can have any value. But as we go down the tree:

  • The left child must be in the range (min, node.val).
  • The right child must be in the range (node.val, max).

Step 3: Apply to a simple valid BST

    2
   /   1   3

We start at node 2:

  • 1 is to the left of 2, and 1 < 2 ✅
  • 3 is to the right of 2, and 3 > 2 ✅

Both children are leaf nodes, so their subtrees are trivially valid. The whole tree is a valid BST.

Step 4: Detect a violation in subtree

    5
   /   1   4
     /     3   6

At first glance, 4 is greater than 5’s left child (1) and less than 5. But dig deeper:

  • Node 3 is in the right subtree of 5 but 3 < 5 ❌

This violates the BST rule. So, even though the tree looks locally correct, it's not a valid BST.

Step 5: Consider deeper boundary checks

    10
   /    5    15
      /       6    20

Node 6 is in the right subtree of 10 but has value 6 < 10 ❌

To detect such violations, we must pass down min and max boundaries during recursion. Here, node 6 violates the range (10, 15).

Step 6: A perfectly balanced valid BST

        8
       /       4   12
     /   /     2  6 10 14

This tree follows all the BST rules:

  • Each node places smaller values on the left and greater values on the right.
  • This rule holds true recursively for all nodes.

Hence, it is a valid BST ✅

Edge Cases

  • Empty Tree: Considered a valid BST. No nodes = no violations.
  • Single Node: Always valid as there are no children to compare.
  • Duplicate Values: Not allowed in a strict BST. If duplicates are allowed, rules must be clearly defined (e.g., duplicates on left or right).
  • Negative and large values: Our range checking should support full integer range.

Finally

To accurately verify whether a tree is a BST, we need to go beyond local comparisons and consider the valid range of values that each node can take, as defined by its ancestors. This is done by recursively checking each node within its permissible min and max boundaries. With this approach, both shallow and deep violations can be caught effectively.

Keep in mind that even a tree that appears valid visually may have subtle rule violations deep in the structure—always think in terms of ranges, not just parent-child values.

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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

bool isBST(TreeNode* root, int min, int max) {
    if (!root) return true;
    if (root->val <= min || root->val >= max) return false;
    return isBST(root->left, min, root->val) && isBST(root->right, root->val, max);
}

int main() {
    TreeNode* root = createNode(2);
    root->left = createNode(1);
    root->right = createNode(3);
    printf("%s\n", isBST(root, INT_MIN, INT_MAX) ? "true" : "false");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...