BST Property and Why It Matters in DSA Typescript - Execution Trace

Concept Flow - BST Property and Why It Matters

Start with root node

↓

Compare new value with current node

↓

Go left

↓

Repeat until null

↓

Insert new node here

↓

BST property maintained

The BST property guides where to insert or find nodes by comparing values and moving left or right, ensuring the tree stays ordered.

Execution Sample

DSA Typescript

Insert 15 into BST:
Start at root (10)
15 >= 10? Go right
Right child is 20
15 < 20? Go left
Left child is null
Insert 15 here

This code inserts a value into a BST by comparing and moving left or right until the correct spot is found.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Start at root	10	N/A	head points to 10	10
2	Compare 15 with 10	10	15 >= 10 → go right	move to right child	10 -> right: 20
3	Compare 15 with 20	20	15 < 20 → go left	move to left child	10 -> 20 -> left: null
4	Insert 15	null	Found null, insert here	left child of 20 = 15	10 -> 20 / 15
5	Done	N/A	BST property maintained	No pointer changes	10 -> 20 / 15

💡 Insertion complete when a null child is found and new node is inserted, maintaining BST property.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
currentNode	10	20	null	15	15
pointerChanges	head -> 10	move to right child (20)	move to left child (null)	left child of 20 = 15	no change
treeSize	3	3	3	4	4

Key Moments - 3 Insights

Why do we move left when the new value is less than the current node?

Because BST property says all left children are smaller, so to keep order, smaller values go left (see execution_table step 3).

What happens if we try to insert a value equal to a node?

By convention, equal or greater values go to the right subtree to keep BST consistent (see execution_table step 2).

Why do we stop when we find a null child?

Null means no node exists there, so it's the correct place to insert the new node without breaking BST rules (see execution_table step 4).

Visual Quiz - 3 Questions

Look at the execution_table, what is the currentNode at step 3?

A 10

B null

C 20

D 15

💡 Hint

Check the 'Current Node' column in execution_table row for step 3.

At which step is the new node actually inserted?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look for the step where pointer changes show a new node assigned (execution_table step 4).

If the new value was 25 instead of 15, which direction would we go from node 20?

A Left

B Right

C Stay at 20

D Insert at 20

💡 Hint

Recall BST property: values greater or equal go right (see concept_flow and execution_table step 2).

Concept Snapshot

BST Property:
- Left child < node
- Right child >= node
Insertion:
- Start at root
- Compare and go left/right
- Insert at null child
Maintains sorted order for fast search.

Full Transcript

The BST property means every node's left child is smaller and right child is equal or bigger. When inserting, start at the root and compare the new value. If smaller, go left; if equal or bigger, go right. Repeat until you find a null child, then insert the new node there. This keeps the tree ordered, making searching efficient. The execution table shows each step: starting at 10, moving right to 20, then left to null, and inserting 15. Variables track current node and pointer changes. Key moments clarify why we move left or right and why insertion stops at null. The quiz tests understanding of these steps. Remember, BST property guides all insertions and searches.

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