BST Property and Why It Matters in DSA Typescript

Mental Model

A Binary Search Tree keeps smaller values on the left and bigger values on the right, making searching fast.

Analogy: Imagine a library where books are arranged so that all books with titles starting before 'M' are on the left shelves, and those after 'M' are on the right shelves. This way, you quickly find any book by checking left or right shelves.

      10
     /  \
    5    15
   / \     \
  3   7     20

Dry Run Walkthrough

Input: BST with nodes 10, 5, 15, 3, 7, 20; search for value 7

Goal: Show how BST property helps find 7 quickly by deciding left or right at each node

Step 1: Start at root node 10

      [10↑]
     /    \
    5      15
   / \       \
  3   7       20

Why: We always start searching from the root

Step 2: Compare 7 with 10, since 7 < 10, go left to node 5

      10
     /    \
   [5↑]    15
   /  \      \
  3    7      20

Why: BST property says smaller values are on the left

Step 3: Compare 7 with 5, since 7 > 5, go right to node 7

      10
     /    \
    5      15
   /  \     \
  3   [7↑]   20

Why: BST property says bigger values are on the right

Step 4: Found node with value 7, stop search

      10
     /    \
    5      15
   /  \     \
  3   [7]   20

Why: We found the value we were looking for

Result:

      10
     /    \
    5      15
   /  \     \
  3    7    20
Answer: Found 7

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if (root === null) return null; // base case: empty tree or not found
  if (root.val === val) return root; // found the value
  if (val < root.val) {
    return searchBST(root.left, val); // go left if val smaller
  } else {
    return searchBST(root.right, val); // go right if val bigger
  }
}

// Build the example tree
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(20);

const result = searchBST(root, 7);
if (result) {
  console.log(`Found ${result.val}`);
} else {
  console.log("Value not found");
}

if (root === null) return null; // base case: empty tree or not found

stop search if reached empty spot

if (root.val === val) return root; // found the value

check if current node has the value

if (val < root.val) { return searchBST(root.left, val); // go left if val smaller } else { return searchBST(root.right, val); // go right if val bigger }

decide direction based on BST property

Output

Found 7

Complexity Analysis

Time: O(h) where h is tree height because we follow one path down the tree

Space: O(h) due to recursion stack in worst case equal to tree height

vs Alternative: Compared to searching an unsorted tree (O(n)), BST search is faster because it skips half the nodes each step

Edge Cases

Empty tree (root is null)

Returns null immediately, meaning value not found

DSA Typescript

if (root === null) return null; // base case: empty tree or not found

Value not present in tree

Search goes down until null and returns null

DSA Typescript

if (root === null) return null; // base case: empty tree or not found

Value is at root node

Returns root immediately without further search

DSA Typescript

if (root.val === val) return root; // found the value

When to Use This Pattern

When you need to quickly find, insert, or delete values in a sorted structure, look for the BST property to guide your search efficiently.

Common Mistakes

Mistake: Not comparing the search value with current node to decide left or right
Fix: Always compare val with node.val to choose the correct subtree

Mistake: Trying to search both left and right subtrees instead of one
Fix: Use BST property to search only one side, reducing time

Summary

It keeps smaller values left and bigger values right to speed up search.

Use it when you want fast searching in a sorted tree structure.

The key is deciding direction by comparing values at each node.