🦄 Starbough: Validate BST

Difficulty: Intermediate Tags: bst, trees, dfs, recursion, binary-tree Series: Data Structures I

Problem

The Starbough's branches grow in perfect order. Validate that a binary tree maintains the Binary Search Tree property: all left descendants < node < all right descendants.

Given a binary tree represented as an array of nodes and a root index, determine if it is a valid Binary Search Tree (BST).

Binary Search Tree Property: - All nodes in left subtree < current node - All nodes in right subtree > current node - Both left and right subtrees must also be BSTs - Duplicates typically not allowed (or treated consistently)

Real-World Application

BST validation is crucial in: - Database indexing - verifying B-tree and B+ tree integrity - File systems - validating directory tree structures - Compiler symbol tables - ensuring lookup correctness - Memory allocators - verifying red-black tree balance - Search engines - validating index structures - Network routing - verifying routing table trees - Operating systems - process tree validation - Data integrity checks - detecting corruption in tree structures

Input

data = {
    'nodes': List[List[int, int, int]],  # [value, left_index, right_index]
    'root': int  # Index of root node
}

Node format: [value, left_child_index, right_child_index] - -1 denotes null child (no left or right child) - Indices refer to positions in the nodes array

Output

bool  # True if valid BST, False otherwise

Constraints

• Node count ≤ 100,000
• Node values are integers (can be negative)
• -1 denotes null child
• Tree may be empty (root = -1)
• Unique node values (no duplicates)

Examples

Example 1: Valid BST

Input:

{
    'nodes': [
        [2, 1, 2],   # Root: value=2, left=index 1, right=index 2
        [1, -1, -1], # Left child: value=1, no children
        [3, -1, -1]  # Right child: value=3, no children
    ],
    'root': 0
}

Output: True

Explanation:

    2
   / \
  1   3

Valid BST: 1 < 2 < 3

Example 2: Invalid BST - Right Child Violation

Input:

{
    'nodes': [
        [5, 1, 2],   # Root: 5
        [1, -1, -1], # Left: 1
        [4, -1, -1]  # Right: 4 (INVALID: 4 < 5 but on right)
    ],
    'root': 0
}

Output: False

Explanation:

    5
   / \
  1   4  ❌ Right child (4) must be > root (5)

Example 3: Invalid BST - Subtree Violation

Input:

{
    'nodes': [
        [5, 1, 2],   # Root: 5
        [3, 3, 4],   # Left subtree root: 3
        [7, -1, -1], # Right: 7
        [2, -1, -1], # Left-left: 2
        [6, -1, -1]  # Left-right: 6 (INVALID!)
    ],
    'root': 0
}

Output: False

Explanation:

      5
     / \
    3   7
   / \
  2   6  ❌ Node 6 is in left subtree of 5, but 6 > 5

Even though 6 > 3 (its parent), it violates BST property because 6 > 5 (ancestor).

Example 4: Single Node

Input:

{
    'nodes': [[10, -1, -1]],
    'root': 0
}

Output: True

Explanation: Single node is always a valid BST.

Example 5: Empty Tree

Input:

{
    'nodes': [],
    'root': -1
}

Output: True

Explanation: Empty tree is considered a valid BST.

Example 6: Left-Skewed Valid BST

Input:

{
    'nodes': [
        [10, 1, -1],
        [5, 2, -1],
        [3, -1, -1]
    ],
    'root': 0
}

Output: True

Explanation:

   10
   /
  5
 /
3

Valid: 3 < 5 < 10

Example 7: Equal Values (Invalid)

Input:

{
    'nodes': [
        [5, 1, 2],
        [5, -1, -1],  # Duplicate value
        [7, -1, -1]
    ],
    'root': 0
}

Output: False

Explanation: Duplicate values violate BST property (strict < and >).

What You'll Learn

• Binary Search Tree properties and invariants
• DFS traversal with constraint propagation
• Using min/max bounds to validate subtrees
• Recursive problem solving with state
• Tree validation techniques

Why This Matters

BST validation is the #3 most common tree interview question at tech companies: - Tests understanding of BST properties - Requires careful handling of edge cases - Demonstrates recursive thinking - Shows ability to work with constraints

Companies that ask this: Amazon, Microsoft, Google, Facebook, Apple, Bloomberg

Starter Code

def challenge_function(data):
    """
    Validate if a binary tree is a valid BST.

    Args:
        data: dict with keys:
            - 'nodes' (List[List[int, int, int]]): array of [value, left_idx, right_idx]
              where -1 denotes null child
            - 'root' (int): index of root node (-1 for empty tree)

    Returns:
        bool: True if valid BST, False otherwise
    """
    # Your implementation here
    pass