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.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. Left child nodes have smaller values, right child nodes have larger values

B. All nodes have exactly two children

C. Nodes are arranged in a circular linked list

D. Each node stores the sum of its children

Solution

1. Step 1: Understand BST node arrangement

   In a BST, every node's left child has a smaller value and the right child has a larger value.

2. Step 2: Compare with other options

   Other options describe different data structures or incorrect properties.

3. Final Answer:

   Left child nodes have smaller values, right child nodes have larger values -> Option A

4. Quick Check:

   BST property = Left smaller, right larger [OK]

Hint: Remember BST orders left < node < right [OK]

Common Mistakes:

• Thinking all nodes must have two children
• Confusing BST with binary tree
• Assuming nodes store sums

2. Which TypeScript interface correctly represents a BST node?

easy

A. interface Node { value: number; parent: Node; }

B. interface Node { value: number; left: Node | null; right: Node | null; }

C. interface Node { value: number; children: Node[]; }

D. interface Node { value: number; next: Node | null; prev: Node | null; }

Solution

1. Step 1: Identify BST node structure

   A BST node has a value and two pointers: left and right, which can be null.

2. Step 2: Check options

   interface Node { value: number; left: Node | null; right: Node | null; } matches this structure; others describe linked lists or generic trees.

3. Final Answer:

   interface Node { value: number; left: Node | null; right: Node | null; } -> Option B

4. Quick Check:

   BST node = value + left + right [OK]

Hint: BST nodes have left and right, not next/prev [OK]

Common Mistakes:

• Using next/prev like linked lists
• Using children array for BST
• Missing null for leaf nodes

3. What will be the in-order traversal output of this BST?

const root = {
  value: 10,
  left: { value: 5, left: null, right: null },
  right: { value: 15, left: null, right: null }
};
function inorder(node) {
  if (!node) return [];
  return [...inorder(node.left), node.value, ...inorder(node.right)];
}
console.log(inorder(root));

medium

A. [10, 5, 15]

B. [5, 15, 10]

C. [15, 10, 5]

D. [5, 10, 15]

Solution

1. Step 1: Understand in-order traversal

   In-order visits left subtree, then node, then right subtree.

2. Step 2: Apply traversal to given tree

   Left subtree: 5, root: 10, right subtree: 15, so output is [5, 10, 15].

3. Final Answer:

   [5, 10, 15] -> Option D

4. Quick Check:

   In-order = left, root, right = [5,10,15] [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Mixing left and right subtree order
• Forgetting to return empty array for null

4. Identify the bug in this BST insertion function:

function insert(node, value) {
  if (!node) return { value, left: null, right: null };
  if (value < node.value) insert(node.left, value);
  else insert(node.right, value);
  return node;
}

medium

A. Node should have a parent pointer

B. Should compare value > node.value instead of <

C. Missing return when recursively inserting left or right

D. Function should not return anything

Solution

1. Step 1: Analyze recursive calls

   The recursive calls to insert do not assign their results back to node.left or node.right.

2. Step 2: Fix missing assignment

   We must assign: node.left = insert(node.left, value) or node.right = insert(node.right, value) to update the tree.

3. Final Answer:

   Missing return when recursively inserting left or right -> Option C

4. Quick Check:

   Recursive insert must update child pointers [OK]

Hint: Always assign recursive insert result to child pointer [OK]

Common Mistakes:

• Not assigning recursive call result
• Wrong comparison operator
• Expecting parent pointer in BST node

5. Given a BST, why is maintaining the BST property important when deleting a node?

hard

A. To ensure in-order traversal still returns sorted values

B. To keep the tree balanced automatically

C. To allow duplicate values in the tree

D. To convert the BST into a linked list

Solution

1. Step 1: Understand BST property role

   The BST property ensures left < node < right, which makes in-order traversal sorted.

2. Step 2: Effect of deletion on BST property

   If deletion breaks this property, in-order traversal won't be sorted, breaking BST usefulness.

3. Final Answer:

   To ensure in-order traversal still returns sorted values -> Option A

4. Quick Check:

   BST property keeps in-order sorted [OK]

Hint: BST property keeps traversal sorted after deletion [OK]

Common Mistakes:

• Thinking BST auto-balances on deletion
• Assuming duplicates are allowed by default
• Confusing BST with linked list