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.