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

Concept Flow - BST Property and Why It Matters

Start at root node

↓

Compare value to node

↓

Go left

↓

Repeat until

↓

Null child found

↓

Insert new node here

The BST property guides where to place or find values by comparing and moving left for smaller or right for larger values until the correct spot is found.

Execution Sample

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

Defines a simple node structure for a BST with value and left/right pointers.

Execution Table

Step	Operation	Current Node Value	Compare With	Pointer Changes	Visual State
1	Start at root	10	Insert 5	None	10
2	Compare 5 < 10	10	5 < 10 is True	Move left pointer	10 / ?
3	Left child is null	null	Insert 5 here	root.left = Node(5)	10 / 5
4	Start at root	10	Insert 15	None	10 / 5
5	Compare 15 > 10	10	15 > 10 is True	Move right pointer	10 / 5 ?
6	Right child is null	null	Insert 15 here	root.right = Node(15)	10 / \ 5 15
7	Start at root	10	Insert 12	None	10 / \ 5 15
8	Compare 12 > 10	10	12 > 10 is True	Move right pointer	10 / \ 5 15 ?
9	Compare 12 < 15	15	12 < 15 is True	Move left pointer	10 / \ 5 15 / ?
10	Left child is null	null	Insert 12 here	15.left = Node(12)	10 / \ 5 15 / 12
11	End	N/A	All inserted	No changes	10 / \ 5 15 / 12

💡 Insertion stops when a null child pointer is found where the new node is attached.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 10	Final
root	Node(10)	Node(10) with left=Node(5)	Node(10) with left=Node(5), right=Node(15)	Node(10) with left=Node(5), right=Node(15 with left=Node(12))	Same as After Step 10
current	Node(10)	null (inserted 5)	null (inserted 15)	null (inserted 12)	null
left child of 10	null	Node(5)	Node(5)	Node(5)	Node(5)
right child of 10	null	null	Node(15)	Node(15)	Node(15)
left child of 15	null	null	null	Node(12)	Node(12)

Key Moments - 3 Insights

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

Because the BST property says smaller values go to the left subtree, as shown in steps 2 and 3 where 5 < 10 leads us left.

What happens if the child pointer is not null when inserting?

We continue moving down the tree following the BST property until we find a null child pointer to insert, as in steps 8 and 9 for inserting 12.

Why is the insertion stopped when we find a null child pointer?

Because that is the correct empty spot to place the new node, ensuring the BST property remains true, as seen in steps 3, 6, and 10.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 6?

A 10 with left child 5 and right child 15

B 10 with right child 15 only

C 10 with left child 5 only

D 10 with left child 12 and right child 15

💡 Hint

Check the Visual State column at step 6 showing both children attached to 10.

At which step does the insertion of the node with value 12 happen?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look for the step where the left child of 15 changes from null to Node(12).

If we tried to insert 20 instead of 12, which direction would we move after step 7?

A Right of 10

B Right of 15

C Left of 15

D Left of 10

💡 Hint

Compare 20 with 10 and 15 following the BST property in the execution table steps.

Concept Snapshot

BST Property:
- Left subtree nodes < parent node
- Right subtree nodes > parent node
- Used to find/insert efficiently
- Insert by comparing and moving left/right
- Stop at null child to insert new node

Full Transcript

The Binary Search Tree (BST) property means every node's left child has a smaller value and right child has a larger value. When inserting a new value, start at the root and compare. If smaller, go left; if larger, go right. Repeat until you find a null child pointer, then insert the new node there. This keeps the tree ordered and allows fast searching and insertion. The execution table shows inserting 5, 15, and 12 into a BST with root 10, moving left or right based on comparisons, and placing nodes at the correct null child pointers.

Practice

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

easy

A. Each node has exactly two children.

B. For each node, all values in the left subtree are smaller, and all values in the right subtree are larger.

C. All nodes have the same value.

D. Nodes are arranged in a circular linked list.

Solution

1. Step 1: Understand BST node value rules

   In a BST, the left subtree contains values smaller than the node, and the right subtree contains values larger than the node.

2. Step 2: Compare options with BST definition

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. matches the BST property exactly, while others describe different structures.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option B

4. Quick Check:

   BST property = left < node < right [OK]

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

Common Mistakes:

• Confusing BST with binary tree (not ordered)
• Thinking all nodes must have two children
• Assuming all values are equal

2. Which of the following is the correct way to check if a value should go to the left subtree in a BST insertion function in JavaScript?

easy

A. if (value < node.value) { insertLeft(); }

B. if (value > node.value) { insertLeft(); }

C. if (value == node.value) { insertLeft(); }

D. if (value >= node.value) { insertLeft(); }

Solution

1. Step 1: Recall BST insertion rule

   Values smaller than the current node go to the left subtree.

2. Step 2: Match condition to insertion side

   Only the condition 'value < node.value' correctly directs insertion to the left.

3. Final Answer:

   if (value < node.value) { insertLeft(); } -> Option A

4. Quick Check:

   Smaller values go left [OK]

Hint: Use < for left subtree insertion [OK]

Common Mistakes:

• Using > instead of < for left subtree
• Using == which is not for left or right
• Using >= which includes equal values incorrectly

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

    10
   /  \
  5   15
 / \    \
3   7    20

medium

A. [20, 15, 10, 7, 5, 3]

B. [10, 5, 3, 7, 15, 20]

C. [3, 5, 7, 10, 15, 20]

D. [5, 3, 7, 10, 15, 20]

Solution

1. Step 1: Understand in-order traversal

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

2. Step 2: Apply in-order to given tree

   Left subtree of 10: 3, 5, 7; then 10; then right subtree: 15, 20. Combined: [3, 5, 7, 10, 15, 20]

3. Final Answer:

   [3, 5, 7, 10, 15, 20] -> Option C

4. Quick Check:

   In-order = sorted BST values [OK]

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

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Listing nodes in insertion order
• Reversing the traversal order

4. Consider this BST insertion code snippet in JavaScript:

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

What is the main issue with this code regarding BST property?

medium

A. It inserts larger values on the left subtree incorrectly.

B. It does not handle the case when node is null.

C. It returns undefined instead of the node.

D. It allows duplicate values on the left subtree, which may break strict BST rules.

Solution

1. Step 1: Analyze duplicate handling in insertion

   The condition 'value <= node.value' inserts duplicates to the left subtree.

2. Step 2: Understand BST strictness

   Strict BSTs require left subtree values strictly less than node value; duplicates on left can break this.

3. Final Answer:

   It allows duplicate values on the left subtree, which may break strict BST rules. -> Option D

4. Quick Check:

   Duplicates on left break strict BST [OK]

Hint: Use < for left to avoid duplicates on left [OK]

Common Mistakes:

• Ignoring duplicate value placement
• Thinking null check is missing
• Confusing left and right subtree insertion

5. You have a BST where some nodes violate the BST property because their left child has a value greater than the node. Which approach best fixes the tree without rebuilding it completely?

hard

A. Swap the values of the violating nodes with their children to restore BST property locally.

B. Ignore the violations as they do not affect search operations.

C. Delete all nodes and insert them again in correct order.

D. Perform an in-order traversal, collect values, then rebuild the BST from sorted values.

Solution

1. Step 1: Understand the violation type

   Left child having greater value than node breaks BST property locally.

2. Step 2: Choose minimal fix without full rebuild

   Swapping values of violating nodes with their children can restore local BST property without full rebuild.

3. Step 3: Evaluate other options

   Perform an in-order traversal, collect values, then rebuild the BST from sorted values. rebuilds fully, Delete all nodes and insert them again in correct order. deletes all nodes (costly), Ignore the violations as they do not affect search operations. ignores problem (wrong).

4. Final Answer:

   Swap the values of the violating nodes with their children to restore BST property locally. -> Option A

5. Quick Check:

   Local swaps fix BST violations efficiently [OK]

Hint: Fix BST by swapping violating node values locally [OK]

Common Mistakes:

• Rebuilding entire tree unnecessarily
• Ignoring violations thinking no impact
• Deleting all nodes instead of fixing