BST Property and Why It Matters in DSA Typescript - Time & Space Complexity

Time Complexity: BST Property and Why It Matters

O(h)

Understanding Time Complexity

We want to understand how the special order in a Binary Search Tree (BST) helps speed up searching and other operations.

How does this order affect the time it takes to find or add items?

Scenario Under Consideration

Analyze the time complexity of searching a value in a BST.

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if (root === null || root.val === val) return root;
  if (val < root.val) return searchBST(root.left, val);
  else return searchBST(root.right, val);
}
    

This code looks for a value by moving left or right depending on comparisons, using the BST order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down one level of the tree.
• How many times: At most once per tree level until the value is found or a leaf is reached.

How Execution Grows With Input

Each step moves down one level, so the number of steps depends on the tree's height.

Input Size (n)	Approx. Operations (steps)
10	About 4 (if balanced)
100	About 7 (if balanced)
1000	About 10 (if balanced)

Pattern observation: In a balanced BST, steps grow slowly (logarithmically) as input grows.

Final Time Complexity

Time Complexity: O(h) where h is tree height

This means the time depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Searching a BST always takes the same time as searching a sorted list."

[OK] Correct: A BST can find values faster by skipping half the tree at each step if balanced, unlike a list which checks items one by one.

Interview Connect

Knowing how the BST property affects search time helps you explain why data structures matter and how to choose the right one for fast lookups.

Self-Check

"What if the BST becomes a linked list (all nodes only have one child)? How would the time complexity change?"

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