Why BST Over Plain Binary Tree in DSA Javascript - See It Work

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of numbers and you want to find, add, or check if a number exists quickly. You can store these numbers in a tree structure. There are two ways: a plain binary tree where numbers are placed randomly, and a Binary Search Tree (BST) where numbers are placed in order.This project will help you see why a BST is better than a plain binary tree for searching numbers.

🎯 Goal: You will create two trees: a plain binary tree and a BST with the same numbers. Then, you will search for a number in both trees and see the difference in how they work.

📋 What You'll Learn

Create a plain binary tree with numbers 10, 5, 15, 3, 7

Create a Binary Search Tree (BST) with the same numbers

Write a function to search for a number in the plain binary tree

Write a function to search for a number in the BST

Print the search result for number 7 in both trees

💡 Why This Matters

🌍 Real World

BSTs are used in databases, file systems, and search engines to quickly find data among many entries.

💼 Career

Understanding BSTs helps in software development roles that require efficient data storage and retrieval, such as backend development and data engineering.

1

Create a Plain Binary Tree

Create a plain binary tree called plainTree with nodes having these exact values and structure:
Root node value 10, left child 5, right child 15, left child of 5 is 3, right child of 5 is 7.
Use objects with value, left, and right properties.

DSA Javascript

// Your code here to create plainTree

Hint

Use nested objects to build the tree. Each node has value, left, and right. Use null for empty children.

2

Create a Binary Search Tree (BST)

Create a Binary Search Tree called bst by inserting the numbers 10, 5, 15, 3, and 7 in that order.
Use a function insertNode(root, value) to insert nodes following BST rules:
- Left child has smaller values
- Right child has larger values
Start with bst = null and insert each number.

DSA Javascript

const plainTree = {
  value: 10,
  left: {
    value: 5,
    left: { value: 3, left: null, right: null },
    right: { value: 7, left: null, right: null }
  },
  right: { value: 15, left: null, right: null }
};

function insertNode(root, value) {
  if (root === null) {
    return { value: value, left: null, right: null };
  }
  if (value < root.value) {
    root.left = insertNode(root.left, value);
  } else {
    root.right = insertNode(root.right, value);
  }
  return root;
}

let bst = null;
// Insert 10, 5, 15, 3, 7 into bst using insertNode
// Your code here

Hint

Use the insertNode function to add each number to bst starting from null.

3

Write Search Functions for Both Trees

Write two functions:
1. searchPlainTree(node, target) that searches for target in the plain binary tree by checking all nodes recursively.
2. searchBST(node, target) that searches for target in the BST using BST rules:
- If target equals current node's value, return true
- If target is less, search left subtree
- If target is greater, search right subtree
Return true if found, otherwise false.

DSA Javascript

const plainTree = {
  value: 10,
  left: {
    value: 5,
    left: { value: 3, left: null, right: null },
    right: { value: 7, left: null, right: null }
  },
  right: { value: 15, left: null, right: null }
};

function insertNode(root, value) {
  if (root === null) {
    return { value: value, left: null, right: null };
  }
  if (value < root.value) {
    root.left = insertNode(root.left, value);
  } else {
    root.right = insertNode(root.right, value);
  }
  return root;
}

let bst = null;
bst = insertNode(bst, 10);
bst = insertNode(bst, 5);
bst = insertNode(bst, 15);
bst = insertNode(bst, 3);
bst = insertNode(bst, 7);

// Write searchPlainTree(node, target) function
// Write searchBST(node, target) function
// Your code here

Hint

For searchPlainTree, check current node, then search left and right children recursively.

For searchBST, use the value comparison to decide which side to search.

4

Print Search Results for Number 7

Print the result of searching for number 7 in both trees.
Use console.log to print:
- searchPlainTree(plainTree, 7)
- searchBST(bst, 7)

DSA Javascript

const plainTree = {
  value: 10,
  left: {
    value: 5,
    left: { value: 3, left: null, right: null },
    right: { value: 7, left: null, right: null }
  },
  right: { value: 15, left: null, right: null }
};

function insertNode(root, value) {
  if (root === null) {
    return { value: value, left: null, right: null };
  }
  if (value < root.value) {
    root.left = insertNode(root.left, value);
  } else {
    root.right = insertNode(root.right, value);
  }
  return root;
}

let bst = null;
bst = insertNode(bst, 10);
bst = insertNode(bst, 5);
bst = insertNode(bst, 15);
bst = insertNode(bst, 3);
bst = insertNode(bst, 7);

function searchPlainTree(node, target) {
  if (node === null) {
    return false;
  }
  if (node.value === target) {
    return true;
  }
  return searchPlainTree(node.left, target) || searchPlainTree(node.right, target);
}

function searchBST(node, target) {
  if (node === null) {
    return false;
  }
  if (node.value === target) {
    return true;
  }
  if (target < node.value) {
    return searchBST(node.left, target);
  } else {
    return searchBST(node.right, target);
  }
}

// Print search results for 7 in both trees
// Your code here

Hint

Use console.log to print the results of searching for 7 in both trees.

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