Why BST Over Plain Binary Tree in DSA Javascript - Why It Works

Concept Flow - Why BST Over Plain Binary Tree

Start with Plain Binary Tree

↓

Insert nodes anywhere

↓

No order: left/right child any value

↓

Search: must check all nodes

↓

Time: O(n) worst case

↓

Switch to BST

↓

Insert nodes with order: left < parent < right

↓

Search: go left or right based on value

↓

Time: O(log n) average

↓

More efficient search, insert, delete

Shows how a plain binary tree inserts nodes without order causing slow search, while BST keeps order for faster search.

Execution Sample

DSA Javascript

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

Defines a node structure used in both plain binary tree and BST.

Execution Table

Step	Operation	Nodes in Tree	Pointer Changes	Visual State
1	Insert 10 in Plain Binary Tree	10	root -> Node(10)	10
2	Insert 5 in Plain Binary Tree (no order)	10, 5	root.left -> Node(5)	10 / 5
3	Insert 15 in Plain Binary Tree (no order)	10, 5, 15	root.right -> Node(15)	10 / \ 5 15
4	Search 15 in Plain Binary Tree	10, 5, 15	Traverse nodes 10 -> 5 -> 15	Must check all nodes until found
5	Insert 10 in BST	10	root -> Node(10)	10
6	Insert 5 in BST (5 < 10)	10, 5	root.left -> Node(5)	10 / 5
7	Insert 15 in BST (15 > 10)	10, 5, 15	root.right -> Node(15)	10 / \ 5 15
8	Search 15 in BST	10, 5, 15	Traverse nodes 10 -> 15 (skip 5)	Search faster by choosing right branch
9	Search 7 in BST (not found)	10, 5, 15	Traverse nodes 10 -> 5 (stop, no right child)	Stops early, no full traversal
10	End	10, 5, 15	No changes	Search and insert efficient in BST

💡 Execution stops after demonstrating search and insert differences between plain binary tree and BST.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 6	After Step 7	After Step 8	Final
root (Plain Binary Tree)	null	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)	Node(10) with left=Node(5), right=Node(15)	Node(10) with left=Node(5), right=Node(15)	Node(10) with left=Node(5), right=Node(15)	Node(10) with left=Node(5), right=Node(15)
root (BST)	null	null	null	null	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)	Node(10) with left=Node(5), right=Node(15)

Key Moments - 3 Insights

Why does searching in a plain binary tree take longer?

Because nodes are inserted without order, search must check every node (see execution_table steps 4 and 9).

How does BST improve search speed?

BST keeps nodes ordered so search goes left or right based on value, skipping many nodes (see execution_table step 8).

Why does BST stop searching early when value not found?

Because it follows order rules, if the path ends without finding the value, it stops early (see execution_table step 9).

Visual Quiz - 3 Questions

Look at the execution table, at which step does BST insert the node with value 5?

A Step 2

B Step 3

C Step 6

D Step 7

💡 Hint

Check the 'Operation' column for BST insertions after step 4.

At which step does searching in the plain binary tree check all nodes?

A Step 8

B Step 4

C Step 9

D Step 6

💡 Hint

Look for 'Search' operation in plain binary tree in the execution_table.

If we insert nodes in BST without order, how would the search time change?

A It would become O(n)

B It would stay O(log n)

C It would become O(1)

D It would be unpredictable

💡 Hint

Refer to key_moments about search efficiency and execution_table steps 4 and 8.

Concept Snapshot

Plain Binary Tree inserts nodes anywhere without order.
Search must check all nodes, time O(n).
BST inserts nodes with order: left < parent < right.
Search goes left or right, time O(log n) average.
BST is faster for search, insert, and delete operations.

Full Transcript

This visual shows why a Binary Search Tree (BST) is better than a plain binary tree. In a plain binary tree, nodes are added anywhere without order, so searching means checking every node, which takes longer. In a BST, nodes are added in order: smaller values go left, bigger go right. This order lets us skip many nodes when searching, making it faster. The execution table shows inserting and searching nodes in both trees, highlighting how BST improves efficiency by reducing the number of nodes checked.

Practice

1. Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching operations?

easy

A. BST does not require pointers to child nodes.

B. BST uses less memory than a plain Binary Tree.

C. BST nodes can have more than two children.

D. BST allows faster search by maintaining sorted order of elements.

Solution

1. Step 1: Understand the structure difference

   A BST keeps elements in sorted order where left child is smaller and right child is larger, unlike a plain Binary Tree which has no order.

2. Step 2: Analyze search efficiency

   Because of this order, BST allows searching by comparing and moving left or right, reducing search time to O(log n) on average, while plain Binary Tree search is O(n).

3. Final Answer:

   BST allows faster search by maintaining sorted order of elements. -> Option D

4. Quick Check:

   BST sorted order = faster search [OK]

Hint: BST keeps order for quick search decisions [OK]

Common Mistakes:

• Thinking BST uses less memory than plain Binary Tree
• Confusing number of children in BST
• Assuming BST nodes don't have child pointers

2. Which of the following is the correct way to check if a node's value is less than the root's value in JavaScript BST code?

easy

A. if (node.value < root.value) {}

B. if node.value < root.value {}

C. if (node.value << root.value) {}

D. if node.value < root.value then {}

Solution

1. Step 1: Identify correct JavaScript syntax for if statement

   JavaScript requires parentheses around the condition and curly braces for the block.

2. Step 2: Check comparison operator and syntax

   The less than operator is <, and it must be inside parentheses: if (condition) {} is correct.

3. Final Answer:

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

4. Quick Check:

   Correct if syntax = if (node.value < root.value) {} [OK]

Hint: Use parentheses and curly braces in if statements [OK]

Common Mistakes:

• Omitting parentheses around condition
• Using incorrect operators like <<
• Writing if without parentheses or braces

3. What will be the output of the following code snippet that inserts values into a BST and then performs an in-order traversal?

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

class BST {
  constructor() {
    this.root = null;
  }
  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }
  inOrder(node, result = []) {
    if (node) {
      this.inOrder(node.left, result);
      result.push(node.value);
      this.inOrder(node.right, result);
    }
    return result;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(7);
console.log(tree.inOrder(tree.root));

medium

A. [5, 7, 10, 15]

B. [10, 5, 7, 15]

C. [15, 10, 7, 5]

D. [7, 5, 10, 15]

Solution

1. Step 1: Insert nodes into BST

   Insert 10 as root, 5 to left of 10, 15 to right of 10, 7 to right of 5.

2. Step 2: Perform in-order traversal

   In-order visits left subtree, root, then right subtree. So order is 5, 7, 10, 15.

3. Final Answer:

   [5, 7, 10, 15] -> Option A

4. Quick Check:

   In-order BST traversal = sorted values [OK]

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

Common Mistakes:

• Confusing traversal order
• Inserting nodes incorrectly
• Expecting pre-order or post-order output

4. The following code attempts to insert a value into a BST but causes an infinite loop. What is the error?

insert(value) {
  const newNode = new Node(value);
  if (!this.root) {
    this.root = newNode;
    return;
  }
  let current = this.root;
  while (true) {
    if (value < current.value) {
      if (!current.left) {
        current.left = newNode;
        break;
      } else {
        current = current.left;
      }
    } else {
      if (!current.right) {
        current.right = newNode;
        break;
      } else {
        current = current.right;
      }
    }
  }
}

medium

A. New node is not created properly.

B. Incorrect comparison operator used.

C. Missing break statement after inserting new node.

D. Root node is not initialized.

Solution

1. Step 1: Analyze loop behavior after insertion

   After assigning newNode to left or right child, loop continues without break, causing infinite loop.

2. Step 2: Identify missing break

   Adding break after insertion stops the loop and prevents infinite iteration.

3. Final Answer:

   Missing break statement after inserting new node. -> Option C

4. Quick Check:

   Break after insert stops infinite loop [OK]

Hint: Add break after insertion to exit loop [OK]

Common Mistakes:

• Forgetting break after insertion
• Changing comparison operators unnecessarily
• Assuming new node creation is faulty

5. You want to store a large set of numbers and perform frequent searches. Why would using a balanced BST be better than a plain Binary Tree or an unbalanced BST?

hard

A. Balanced BST uses less memory than unbalanced BST.

B. Balanced BST guarantees O(log n) search time, unlike unbalanced BST or plain Binary Tree.

C. Balanced BST allows nodes to have multiple parents for faster access.

D. Balanced BST does not require pointers to child nodes.

Solution

1. Step 1: Understand search time in different trees

   Plain Binary Tree search is O(n), unbalanced BST can degrade to O(n) if skewed, balanced BST keeps height low.

2. Step 2: Benefit of balanced BST

   Balanced BST maintains height around log n, ensuring search, insert, delete operations are O(log n) consistently.

3. Final Answer:

   Balanced BST guarantees O(log n) search time, unlike unbalanced BST or plain Binary Tree. -> Option B

4. Quick Check:

   Balanced BST = consistent fast search [OK]

Hint: Balance keeps tree height low for fast search [OK]

Common Mistakes:

• Thinking balanced BST uses less memory
• Believing nodes can have multiple parents
• Assuming no child pointers needed