BST Insert Operation in DSA Javascript - Execution Trace

Concept Flow - BST Insert Operation

Start at root

↓

Compare new value with current node

↓

Go left

↓

Is child null?

↓

Insert new node

↩Back to Compare

Start at the root, compare the new value with current node, go left if smaller, right if greater or equal, repeat until a null child is found, then insert the new node there.

Execution Sample

DSA Javascript

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

function insert(root, value) {
  if (!root) return new Node(value);
  if (value < root.data) root.left = insert(root.left, value);
  else root.right = insert(root.right, value);
  return root;
}

This code inserts a value into a BST by recursively finding the correct position and adding a new node.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Tree State
1	Start at root	50	50 ? 30	None	50 / ∅ ∅
2	Compare 30 < 50	50	30 < 50 → go left	None	50 / ∅ ∅
3	Left child is null, insert 30	50	Left child null	50.left → Node(30)	50 / 30 ∅
4	Insert complete	30	Inserted at left of 50	None	50 / 30 ∅

💡 Insertion done when a null child is found and new node is linked.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
root	Node(50)	Node(50)	Node(50)	Node(50)
current	Node(50)	Node(50)	null (left child)	Node(30) inserted
root.left	null	null	Node(30)	Node(30)

Key Moments - 3 Insights

Why do we check if the left or right child is null before inserting?

Because the new node must be inserted at a position where there is no existing child. The execution_table row 3 shows insertion happens only when left child is null.

What happens if the new value is equal to a node's data?

The code treats equal values as greater or equal and moves to the right child. This is shown in the concept_flow where 'Greater or Equal' leads right.

Why do we return the root after insertion?

Returning the root ensures the tree structure is maintained and updated correctly up the recursive calls, as seen in the code sample.

Visual Quiz - 3 Questions

Look at the execution_table, what is the tree state after step 3?

A 30 as root node only

B 50 with no children

C 50 with left child 30 and right child null

D Empty tree

💡 Hint

Check the 'Tree State' column in row 3 of execution_table

At which step does the insertion actually happen?

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look for 'insert' or 'Pointer Changes' in execution_table rows

If we insert 70 instead of 30, which direction will the traversal go from root 50?

A Left

B Right

C No movement, insert at root

D Both left and right

💡 Hint

Refer to concept_flow where values greater or equal go right

Concept Snapshot

BST Insert Operation:
- Start at root node
- Compare new value with current node
- Go left if smaller, right if greater or equal
- Repeat until null child found
- Insert new node at null position
- Return root to maintain tree structure

Full Transcript

The BST Insert Operation starts at the root node. We compare the new value with the current node's data. If the new value is smaller, we move to the left child; if greater or equal, we move to the right child. We continue this until we find a null child pointer, where we insert the new node. The root is returned to maintain the tree structure. The execution table shows step-by-step how the tree changes, including pointer updates and the tree's visual state. Key moments clarify why we check for null children before insertion, how equal values are handled, and why returning the root is important.

Practice

1. What does the insert operation do in a Binary Search Tree (BST)?

easy

A. Searches for a node with a given value

B. Adds a new node in the correct position to maintain BST order

C. Deletes a node from the tree

D. Balances the tree automatically after insertion

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Purpose of insert operation

   The insert operation places a new value in the tree so that this property remains true.

3. Final Answer:

   Adds a new node in the correct position to maintain BST order -> Option B

4. Quick Check:

   Insert means add node correctly [OK]

Hint: Insert means add node keeping BST order intact [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert searches only without adding

2. Which of the following is the correct syntax to insert a value val into a BST node root in JavaScript?

easy

A. root = insert(root, val);

B. root.insert(val);

C. insert(root, val);

D. insert(val, root);

Solution

1. Step 1: Understand function usage in BST insert

   Insert usually returns the new root after insertion, so assignment is needed.

2. Step 2: Check parameter order and assignment

   The function takes the root and value, returns updated root, so root = insert(root, val); is correct.

3. Final Answer:

   root = insert(root, val); -> Option A

4. Quick Check:

   Assign updated root after insert [OK]

Hint: Insert returns new root, so assign it back [OK]

Common Mistakes:

• Calling insert without assignment
• Passing parameters in wrong order
• Using method call on root without method defined

3. What will be the inorder traversal output after inserting 5 into this BST?

    10
   /  
  3    15
   
    4

Insert 5 and then print inorder traversal.

medium

A. [3, 5, 4, 10, 15]

B. [3, 4, 10, 5, 15]

C. [3, 4, 5, 10, 15]

D. [5, 3, 4, 10, 15]

Solution

1. Step 1: Insert 5 into BST

   Start at root 10, 5 < 10 go left to 3, 5 > 3 go right to 4, 5 > 4 insert as right child of 4.

2. Step 2: Perform inorder traversal

   Inorder visits left, root, right: nodes visited in order: 3, 4, 5, 10, 15.

3. Final Answer:

   [3, 4, 5, 10, 15] -> Option C

4. Quick Check:

   Inorder sorted after insert [OK]

Hint: Inorder traversal of BST is sorted list [OK]

Common Mistakes:

• Inserting 5 as left child of 4
• Mixing preorder or postorder traversal output
• Ignoring BST property during insertion

4. Given this insert function snippet, what is the error?

function insert(root, val) {
  if (root == null) {
    return new Node(val);
  }
  if (val < root.val) {
    insert(root.left, val);
  } else {
    insert(root.right, val);
  }
  return root;
}

medium

A. Returning root before insertion

B. Incorrect base case condition

C. Using '==' instead of '===' for null check

D. Missing assignment of recursive insert result to root.left or root.right

Solution

1. Step 1: Check recursive calls

   Recursive calls to insert do not assign the returned node back to root.left or root.right, so tree structure won't update.

2. Step 2: Correct recursive assignment

   Should assign: root.left = insert(root.left, val); or root.right = insert(root.right, val); to update links.

3. Final Answer:

   Missing assignment of recursive insert result to root.left or root.right -> Option D

4. Quick Check:

   Assign recursive insert result to child [OK]

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

Common Mistakes:

• Ignoring assignment in recursion
• Confusing base case with recursive step
• Thinking '==' causes error here

5. You have a BST with nodes 20, 10, 30. You insert 25, then 5, then 35. What is the preorder traversal of the BST after all insertions?

hard

A. [20, 10, 5, 30, 25, 35]

B. [20, 30, 25, 35, 10, 5]

C. [10, 5, 20, 30, 25, 35]

D. [20, 10, 30, 5, 25, 35]

Solution

1. Step 1: Insert nodes step-by-step

   Start with root 20, left 10, right 30.
   Insert 25: 25 < 30 and > 20, goes left of 30.
   Insert 5: less than 10, goes left of 10.
   Insert 35: greater than 30, goes right of 30.

2. Step 2: Preorder traversal

   Preorder visits root, left subtree, right subtree.
   Visit 20, then left subtree (10, 5), then right subtree (30, 25, 35).
   So preorder: [20, 10, 5, 30, 25, 35]

3. Final Answer:

   [20, 10, 5, 30, 25, 35] -> Option A

4. Quick Check:

   Preorder = root-left-right [OK]

Hint: Preorder = root, left subtree, right subtree [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder
• Inserting nodes in wrong position
• Forgetting to update tree after insert