Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

BST Fundamentals & Properties

EASYProblemSolveExternal Links

Description

A Binary Search Tree (BST) is a binary tree where every node satisfies a strict ordering rule:

  • All values in the left subtree of a node are strictly less than the node's value.
  • All values in the right subtree of a node are strictly greater than the node's value.
  • Both the left and right subtrees must themselves be valid BSTs.
  • All node values are distinct.

Given the root of a binary tree, determine whether it is a valid Binary Search Tree.

A common mistake is to only check if each node's left child is smaller and right child is larger. This is not sufficient — the BST property must hold for the entire left and right subtrees, not just the immediate children.

Side-by-side comparison of a valid BST and an invalid binary tree that looks like a BST at first glance
Side-by-side comparison of a valid BST and an invalid binary tree that looks like a BST at first glance

Examples

Example 1

Input:

      4
     / \
    2   6
   / \ / \
  1  3 5  7

Output: true

Explanation: For every node, all values in its left subtree are smaller and all values in its right subtree are larger. For instance, node 6 has left child 5 (5 < 6) and right child 7 (7 > 6), and both 5 and 7 are also greater than 4 (the root), satisfying the BST property with respect to all ancestors.

Example 2

Input:

      10
     /  \
    5   15
   / \
  2   12

Output: false

Explanation: Node 12 is in the left subtree of the root (10), but 12 > 10. Even though 12 is correctly placed as the right child of 5 (12 > 5), it violates the BST property with respect to the root. All nodes in the left subtree of 10 must be less than 10.

Example 3

Input:

    5

Output: true

Explanation: A single node with no children is trivially a valid BST — there are no subtree constraints to violate.

Example 4

Input:

      5
     / \
    4   6
       / \
      3   7

Output: false

Explanation: Node 3 is in the right subtree of root 5, but 3 < 5. Even though 3 < 6 (its parent), it violates the constraint that all right-subtree values of 5 must be greater than 5.

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • -2^31 ≤ node.val ≤ 2^31 - 1
  • All node values are distinct

Editorial

Brute Force

Intuition

The most direct way to verify a BST is to literally check the definition for every node: for each node, scan its entire left subtree to confirm every value there is smaller, and scan its entire right subtree to confirm every value there is larger.

Think of it like a classroom seating arrangement. The rule says everyone to the left of a student must have a smaller roll number, and everyone to the right must have a larger one. The brute force way to verify this is to walk down the entire left aisle and right aisle for every single student, checking one by one.

This is correct but extremely repetitive — we keep re-visiting the same nodes over and over for different ancestor checks.

Step-by-Step Explanation

Let's trace through the invalid tree from Example 2:

      10
     /  \
    5   15
   / \
  2   12

Step 1: Start at root (10). Check entire left subtree for values < 10. Left subtree contains: 5, 2, 12. Scan them one by one.

Step 2: Check 5 < 10? Yes. Check 2 < 10? Yes. Check 12 < 10? NO! 12 ≥ 10.

Step 3: The left subtree of node 10 contains a value (12) that is not less than 10. This violates the BST property.

Result: Return false.

Now let's also trace a valid case — Example 1:

      4
     / \
    2   6
   / \ / \
  1  3 5  7

Step 4: Start at root (4). Scan left subtree: {2, 1, 3}. All < 4? Yes. Scan right subtree: {6, 5, 7}. All > 4? Yes.

Step 5: Move to node 2. Scan left subtree: {1}. All < 2? Yes. Scan right subtree: {3}. All > 2? Yes.

Step 6: Move to node 6. Scan left subtree: {5}. All < 6? Yes. Scan right subtree: {7}. All > 6? Yes.

Step 7: Nodes 1, 3, 5, 7 are leaves — no subtrees to check.

Result: All nodes pass the check. Return true.

Brute Force — Scanning Subtrees for Each Node — Watch how the brute force approach repeatedly traverses subtrees to verify the BST property at each node, leading to redundant work.

Algorithm

  1. For each node in the tree:
    a. Traverse the entire left subtree and verify every value is less than the current node's value.
    b. Traverse the entire right subtree and verify every value is greater than the current node's value.
    c. If any violation is found, return false.
  2. Recursively apply the same check to the left child and right child.
  3. If all nodes pass, return true.

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Check if all values in the subtree are less than 'val'
    bool allLessThan(Node* node, int val) {
        if (!node) return true;
        if (node->data >= val) return false;
        return allLessThan(node->left, val) && allLessThan(node->right, val);
    }

    // Check if all values in the subtree are greater than 'val'
    bool allGreaterThan(Node* node, int val) {
        if (!node) return true;
        if (node->data <= val) return false;
        return allGreaterThan(node->left, val) && allGreaterThan(node->right, val);
    }

    bool isBST(Node* root) {
        if (!root) return true;

        // Check that all left-subtree values < root
        // and all right-subtree values > root
        if (!allLessThan(root->left, root->data)) return false;
        if (!allGreaterThan(root->right, root->data)) return false;

        // Recursively verify children
        return isBST(root->left) && isBST(root->right);
    }
};
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

class Solution:
    def all_less_than(self, node, val):
        """Check if all values in subtree are less than val."""
        if not node:
            return True
        if node.data >= val:
            return False
        return (self.all_less_than(node.left, val) and
                self.all_less_than(node.right, val))

    def all_greater_than(self, node, val):
        """Check if all values in subtree are greater than val."""
        if not node:
            return True
        if node.data <= val:
            return False
        return (self.all_greater_than(node.left, val) and
                self.all_greater_than(node.right, val))

    def isBST(self, root):
        if not root:
            return True

        if not self.all_less_than(root.left, root.data):
            return False
        if not self.all_greater_than(root.right, root.data):
            return False

        return self.isBST(root.left) and self.isBST(root.right)
class Node {
    int data;
    Node left, right;
    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    boolean allLessThan(Node node, int val) {
        if (node == null) return true;
        if (node.data >= val) return false;
        return allLessThan(node.left, val) && allLessThan(node.right, val);
    }

    boolean allGreaterThan(Node node, int val) {
        if (node == null) return true;
        if (node.data <= val) return false;
        return allGreaterThan(node.left, val) && allGreaterThan(node.right, val);
    }

    boolean isBST(Node root) {
        if (root == null) return true;

        if (!allLessThan(root.left, root.data)) return false;
        if (!allGreaterThan(root.right, root.data)) return false;

        return isBST(root.left) && isBST(root.right);
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each node, we potentially scan its entire subtree to verify the BST property. In the worst case (a skewed tree), the root scans n-1 nodes, then its child scans n-2, and so on. This gives us n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²).

Even for a balanced tree, each level-k node scans approximately n/2^k nodes, leading to O(n log n) work — still not optimal.

Space Complexity: O(h)

The recursion stack depth equals the height h of the tree. For a balanced tree h = O(log n), for a skewed tree h = O(n).

Why This Approach Is Not Efficient

The brute force is O(n²) because it repeatedly traverses the same subtrees. When we check the root, we scan every node. Then when we check the root's left child, we scan its subtree again — even though we just visited those same nodes moments ago.

The fundamental waste: each node is visited once by its own check, plus once for every ancestor's check. A node at depth d gets scanned d+1 times total.

We need a way to verify each node exactly once. The key insight comes from a fundamental property of BSTs: if you traverse a BST in inorder (left → root → right), the values come out in sorted ascending order. So instead of checking the BST property directly, we can check whether the inorder traversal produces a sorted sequence.

Better Approach - Inorder Traversal

Intuition

One of the most elegant properties of a BST is that its inorder traversal (visit left subtree, then current node, then right subtree) produces values in strictly ascending order.

This gives us a much simpler validation strategy: perform an inorder traversal and check that each value is strictly greater than the previous one. If at any point we see a value that is less than or equal to the previous value, the tree is not a BST.

Think of it like reading names from an alphabetically sorted bookshelf by going left-to-right. If you ever encounter a book that comes before the previous one alphabetically, the shelf is not sorted correctly.

We don't even need to store the entire traversal in an array. We can simply keep track of the previously visited value during the traversal and compare each new value against it.

Step-by-Step Explanation

Let's trace the valid BST from Example 1:

      4
     / \
    2   6
   / \ / \
  1  3 5  7

Step 1: Initialize prev = -∞ (negative infinity). Start inorder traversal at root (4).

Step 2: Go left to node 2. Go left again to node 1. Node 1 has no left child — visit node 1. Is 1 > prev (-∞)? Yes. Update prev = 1.

Step 3: Backtrack to node 2. Visit node 2. Is 2 > prev (1)? Yes. Update prev = 2.

Step 4: Go right to node 3. Node 3 has no children — visit node 3. Is 3 > prev (2)? Yes. Update prev = 3.

Step 5: Backtrack to root (4). Visit node 4. Is 4 > prev (3)? Yes. Update prev = 4.

Step 6: Go right to node 6. Go left to node 5. Visit node 5. Is 5 > prev (4)? Yes. Update prev = 5.

Step 7: Backtrack to node 6. Visit node 6. Is 6 > prev (5)? Yes. Update prev = 6.

Step 8: Go right to node 7. Visit node 7. Is 7 > prev (6)? Yes. Update prev = 7.

Result: Every value was strictly greater than the previous one. The inorder sequence is [1, 2, 3, 4, 5, 6, 7] — sorted! Return true.

Inorder Traversal — Checking Sorted Order — Watch how the inorder traversal visits nodes in ascending order. Each node's value is compared against the previously visited value to verify the BST property.

Algorithm

  1. Initialize a variable prev to negative infinity (or use a pointer/reference).
  2. Perform an inorder traversal of the tree:
    a. Recursively traverse the left subtree. If it returns false, propagate false.
    b. Visit the current node. If the current node's value is ≤ prev, return false.
    c. Update prev to the current node's value.
    d. Recursively traverse the right subtree. If it returns false, propagate false.
  3. If the entire traversal completes without violation, return true.

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool inorder(Node* root, int& prev) {
        if (!root) return true;

        // Traverse left subtree
        if (!inorder(root->left, prev)) return false;

        // Check current node against previous value
        if (prev >= root->data) return false;
        prev = root->data;

        // Traverse right subtree
        return inorder(root->right, prev);
    }

    bool isBST(Node* root) {
        int prev = INT_MIN;
        return inorder(root, prev);
    }
};
import math

class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

class Solution:
    def isBST(self, root):
        self.prev = -math.inf
        return self._inorder(root)

    def _inorder(self, node):
        if not node:
            return True

        # Traverse left subtree
        if not self._inorder(node.left):
            return False

        # Check current node against previous value
        if self.prev >= node.data:
            return False
        self.prev = node.data

        # Traverse right subtree
        return self._inorder(node.right)
class Node {
    int data;
    Node left, right;
    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    int prev = Integer.MIN_VALUE;

    boolean inorder(Node root) {
        if (root == null) return true;

        // Traverse left subtree
        if (!inorder(root.left)) return false;

        // Check current node against previous value
        if (prev >= root.data) return false;
        prev = root.data;

        // Traverse right subtree
        return inorder(root.right);
    }

    boolean isBST(Node root) {
        prev = Integer.MIN_VALUE;
        return inorder(root);
    }
}

Complexity Analysis

Time Complexity: O(n)

The inorder traversal visits each of the n nodes exactly once. At each node, we do a constant-time comparison and update. Total: O(n).

This is a massive improvement from the brute force's O(n²) — we eliminated all redundant subtree scans.

Space Complexity: O(h)

The space is dominated by the recursion stack, which goes as deep as the height of the tree. For a balanced BST, h = O(log n). For a skewed tree (worst case), h = O(n).

We use only one extra variable (prev) beyond the recursion stack, so the auxiliary space is purely the stack depth.

Why This Approach Is Not Efficient

The inorder traversal approach is already O(n) in time and O(h) in space, which is optimal for this problem — we must visit every node at least once to verify the BST property.

However, there is an alternative approach that is equally efficient but provides a different perspective and is often preferred in interviews because it directly encodes the BST invariant. Instead of relying on a global prev variable and the observation that inorder traversal yields sorted order, we can pass down explicit valid ranges for each node.

The range-based approach is more intuitive in some ways: it directly answers the question "what values is this node allowed to have?" rather than using the indirect sorted-order property. It also naturally handles edge cases (like INT_MIN/INT_MAX boundary values) by using long or nullable bounds.

Optimal Approach - Range Validation

Intuition

The most direct way to validate a BST is to pass down a valid range for each node as we traverse the tree.

The root can hold any value, so its range is (-∞, +∞). When we go left from a node with value V, the left child's value must be less than V, so the range narrows to (-∞, V). When we go right, the right child must be greater than V, so the range becomes (V, +∞).

As we go deeper, the range keeps narrowing. Each node inherits a range from all of its ancestors. If the node's value falls outside this range, the tree is not a BST.

Think of it like a hallway getting narrower. The root is a wide-open space. Each turn (left or right) puts up a wall, making the valid zone smaller. If a node doesn't fit in the remaining corridor, it's in the wrong place.

This approach elegantly encodes the complete BST invariant — that every node must satisfy constraints from all ancestors — in a single recursive pass with just two parameters.

Step-by-Step Explanation

Let's trace the invalid tree from Example 2:

      10
     /  \
    5   15
   / \
  2   12

Step 1: Start at root (10) with range (-∞, +∞). Is 10 in range? Yes.

Step 2: Go left to node 5. Range narrows to (-∞, 10). Is 5 in (-∞, 10)? Yes (5 < 10).

Step 3: Go left from 5 to node 2. Range narrows to (-∞, 5). Is 2 in (-∞, 5)? Yes (2 < 5).

Step 4: Node 2 has no children. Backtrack to node 5. Go right to node 12. Range is (5, 10) — must be > 5 (right of 5) AND < 10 (left of 10).

Step 5: Is 12 in (5, 10)? NO! 12 > 10, which violates the upper bound.

Step 6: Return false immediately.

Result: The tree is NOT a valid BST because node 12 exceeds the upper bound inherited from root 10.

Now trace the valid BST from Example 1:

      4
     / \
    2   6
   / \ / \
  1  3 5  7

Step 7: Root 4, range (-∞, +∞). Valid.

Step 8: Node 2, range (-∞, 4). 2 < 4. Valid.

Step 9: Node 1, range (-∞, 2). 1 < 2. Valid. (Leaf — done.)

Step 10: Node 3, range (2, 4). 2 < 3 < 4. Valid. (Leaf — done.)

Step 11: Node 6, range (4, +∞). 6 > 4. Valid.

Step 12: Node 5, range (4, 6). 4 < 5 < 6. Valid. (Leaf — done.)

Step 13: Node 7, range (6, +∞). 7 > 6. Valid. (Leaf — done.)

Result: All nodes fall within their valid ranges. Return true.

Range Validation — Narrowing Valid Bounds at Each Level — Watch how the valid range narrows as we descend the tree. Going left tightens the upper bound; going right tightens the lower bound. Node 12 exceeds its allowed range.

Algorithm

  1. Define a recursive helper function validate(node, low, high) where low and high represent the valid range for the node's value.
  2. Base case: If the node is null, return true (empty tree is valid).
  3. Range check: If node.val ≤ low or node.val ≥ high, return false.
  4. Recurse left: Call validate(node.left, low, node.val) — the left child's upper bound is the current node's value.
  5. Recurse right: Call validate(node.right, node.val, high) — the right child's lower bound is the current node's value.
  6. Return true only if both recursive calls return true.
  7. Initial call: validate(root, -∞, +∞).

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool validate(Node* node, long low, long high) {
        // Base case: empty tree is valid
        if (!node) return true;

        // Check if current node is within valid range
        if (node->data <= low || node->data >= high) {
            return false;
        }

        // Left child must be in range (low, node->data)
        // Right child must be in range (node->data, high)
        return validate(node->left, low, node->data) &&
               validate(node->right, node->data, high);
    }

    bool isBST(Node* root) {
        return validate(root, LONG_MIN, LONG_MAX);
    }
};
import math

class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

class Solution:
    def isBST(self, root):
        return self._validate(root, -math.inf, math.inf)

    def _validate(self, node, low, high):
        # Base case: empty tree is valid
        if not node:
            return True

        # Check if current node is within valid range
        if node.data <= low or node.data >= high:
            return False

        # Left child range: (low, node.data)
        # Right child range: (node.data, high)
        return (self._validate(node.left, low, node.data) and
                self._validate(node.right, node.data, high))
class Node {
    int data;
    Node left, right;
    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    boolean validate(Node node, long low, long high) {
        // Base case: empty tree is valid
        if (node == null) return true;

        // Check if current node is within valid range
        if (node.data <= low || node.data >= high) {
            return false;
        }

        // Left child range: (low, node.data)
        // Right child range: (node.data, high)
        return validate(node.left, low, node.data) &&
               validate(node.right, node.data, high);
    }

    boolean isBST(Node root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once. At each node, we perform two constant-time comparisons (against low and high) and two recursive calls. Total: O(n).

Space Complexity: O(h)

The space is used by the recursion stack, which goes as deep as the height of the tree. For a balanced BST, h = O(log n). For a completely skewed tree (worst case), h = O(n).

No additional data structures are used — only the two range parameters (low, high) are passed down the recursion, which is O(1) extra per frame.

This matches the inorder approach in both time and space complexity, but the range-based approach is often considered more elegant because it directly encodes the BST invariant (each node must fall within a valid range determined by all its ancestors) without relying on the indirect property of sorted inorder traversal.