Why BST Over Plain Binary Tree in DSA Typescript - 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. A plain binary tree stores numbers without any order, while a Binary Search Tree (BST) keeps numbers in order to speed up searching.

🎯 Goal: Build two simple tree structures: a plain binary tree and a binary search tree (BST). Then, compare how searching for a number works in both. This will show why BST is better for quick searches.

📋 What You'll Learn

Create a plain binary tree with specific nodes

Create a binary search tree (BST) with the same nodes in order

Write a search function for both trees

Search for a number in both trees and print the results

💡 Why This Matters

🌍 Real World

Binary search trees are used in databases and file systems to quickly find data without checking every item.

💼 Career

Understanding BSTs helps in software engineering roles that involve data storage, search optimization, and algorithm design.

1

Create a plain binary tree

Create a plain binary tree using the TreeNode class with these exact nodes: root node with value 10, left child 5, right child 15, left child of 5 is 3, right child of 5 is 7.

DSA Typescript

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Create plain binary tree nodes
// Your code here

Hint

Use the TreeNode class to create nodes and link them by setting left and right properties.

2

Create a binary search tree (BST)

Create a binary search tree (BST) by inserting these values in order: 10, 5, 15, 3, 7. Use the insertBST function to place nodes correctly.

DSA Typescript

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function insertBST(root: TreeNode | null, value: number): TreeNode {
  if (root === null) {
    return new TreeNode(value);
  }
  if (value < root.value) {
    root.left = insertBST(root.left, value);
  } else {
    root.right = insertBST(root.right, value);
  }
  return root;
}

// Create BST by inserting values
// Your code here

Hint

Use the insertBST function to add each value to the BST starting from null for the root.

3

Write search functions for both trees

Write two search functions: searchPlain to search the plain binary tree and searchBST to search the BST. Both take a TreeNode | null and a number value, and return true if found, false otherwise.

DSA Typescript

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Write searchPlain function
// Write searchBST function
// Your code here

Hint

Use recursion to check nodes. For searchPlain, check both left and right children. For searchBST, decide direction based on value comparison.

4

Search for a number and print results

Use searchPlain and searchBST to search for the number 7 in both trees. Print the results exactly as: "Plain Tree: true" and "BST: true".

DSA Typescript

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

Hint

Call both search functions with 7 and print results exactly as shown.