BST Search Operation in DSA Javascript - Build from Scratch

BST Search Operation

📖 Scenario: You are working with a simple phone book application that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number as the key.You want to find if a particular phone number exists in the phone book.

🎯 Goal: Build a program that creates a BST with given phone numbers, sets a target phone number to search, performs the search operation, and prints whether the number is found or not.

📋 What You'll Learn

Create a BST node class with value, left, and right properties

Manually create a BST with the exact phone numbers: 50, 30, 70, 20, 40, 60, 80

Create a variable target with the phone number to search: 60

Write a function searchBST that takes the root node and the target value and returns true if found, otherwise false

Print Found if the target is in the BST, else print Not Found

💡 Why This Matters

🌍 Real World

BSTs are used in phone books, contact lists, and databases to quickly find information by key.

💼 Career

Understanding BST search is important for software engineers working with data storage, search engines, and optimization.

1

Create BST nodes and build the tree

Create a class called Node with a constructor that takes value and sets left and right to null. Then create nodes with values 50, 30, 70, 20, 40, 60, and 80. Connect them to form the BST as shown: 50 is root, 30 is left child of 50, 70 is right child of 50, 20 is left child of 30, 40 is right child of 30, 60 is left child of 70, and 80 is right child of 70.

DSA Javascript

// Your code here

Hint

Define the Node class first. Then create the root node with value 50. Attach left and right children as described.

2

Set the target phone number to search

Create a variable called target and set it to the number 60.

DSA Javascript

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

// Your code here

Hint

Just create a variable named target and assign it the value 60.

3

Write the search function for BST

Write a function called searchBST that takes two parameters: node and target. It should return true if target is found in the BST starting at node, otherwise false. Use the BST property: if target is less than node.value, search the left subtree; if greater, search the right subtree; if equal, return true. If node is null, return false.

DSA Javascript

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

const target = 60;

// Write searchBST function here

Hint

Use recursion to check if the target is found. Return true if found, false if you reach a null node.

4

Print the search result

Use console.log to print Found if searchBST(root, target) returns true, otherwise print Not Found.

DSA Javascript

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.left = new Node(60);
root.right.right = new Node(80);

const target = 60;

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

// Print the result below
// Your code here

Hint

Call searchBST with root and target. Print "Found" if true, else "Not Found".

Practice

1. What is the main purpose of the search operation in a Binary Search Tree (BST)?

easy

A. To insert a new value into the BST

B. To find whether a given value exists in the BST

C. To delete a value from the BST

D. To balance the BST

Solution

1. Step 1: Understand the search operation

   The search operation in a BST is used to check if a specific value is present in the tree.

2. Step 2: Differentiate from other operations

   Insertion adds new values, deletion removes values, and balancing adjusts the tree structure. Search only checks for existence.

3. Final Answer:

   To find whether a given value exists in the BST -> Option B

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search changes the tree
• Assuming search balances the tree

2. Which of the following is the correct syntax to start a search function for a BST node in JavaScript?

easy

A. function searchBST(value, root) { }

B. function searchBST(value) { return root; }

C. function searchBST(root) { return value; }

D. function searchBST(root, value) { }

Solution

1. Step 1: Identify parameters needed for BST search

   The search needs the root node to start and the value to find, so parameters are (root, value).

2. Step 2: Check function signature correctness

   function searchBST(root, value) { } correctly uses (root, value). Options A, C, and D have wrong parameter order or missing parameters.

3. Final Answer:

   function searchBST(root, value) { } -> Option D

4. Quick Check:

   Correct parameters order = function searchBST(root, value) { } [OK]

Hint: Root node first, value second in search function [OK]

Common Mistakes:

• Swapping parameter order
• Missing one parameter
• Returning wrong variable immediately

3. Consider the following BST and the search code snippet:

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

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);

function searchBST(root, val) {
  if (!root) return false;
  if (root.val === val) return true;
  if (val < root.val) return searchBST(root.left, val);
  else return searchBST(root.right, val);
}

console.log(searchBST(root, 15));

What will be the output?

medium

A. true

B. false

C. undefined

D. Error

Solution

1. Step 1: Trace the search for value 15

   Start at root (10). Since 15 > 10, move to right child (15).

2. Step 2: Check if current node value matches 15

   Node value is 15, which matches the search value, so return true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Value found = true [OK]

Hint: Compare value with node, go left or right [OK]

Common Mistakes:

• Returning false too early
• Not checking node value before recursion
• Confusing left and right child directions

4. The following code is intended to search a value in a BST but does not work correctly. What is the error?

function searchBST(root, val) {
  if (root === null) return false;
  if (root.val === val) return true;
  if (val > root.val) return searchBST(root.left, val);
  else return searchBST(root.right, val);
}

medium

A. Incorrect return type

B. Missing base case for empty tree

C. The comparison directions for left and right child are swapped

D. Function parameters are wrong

Solution

1. Step 1: Analyze comparison logic for recursion

   If val > root.val, search should go right, but code goes left. This is reversed.

2. Step 2: Confirm correct child direction for BST search

   For val > root.val, search right subtree; for val < root.val, search left subtree.

3. Final Answer:

   The comparison directions for left and right child are swapped -> Option C

4. Quick Check:

   Left/right child direction swapped = The comparison directions for left and right child are swapped [OK]

Hint: Greater value goes right, smaller goes left [OK]

Common Mistakes:

• Swapping left and right child in recursion
• Forgetting base case
• Returning wrong data type

5. You have a BST with nodes: 20 (root), 10 (left child), 30 (right child), 5 (left of 10), 15 (right of 10). You want to search for value 12. Which nodes will the search visit in order?

hard

A. 20 -> 10 -> 15

B. 20 -> 30 -> 15

C. 20 -> 10 -> 5

D. 20 -> 15 -> 10

Solution

1. Step 1: Start at root node 20 and compare with 12

   Since 12 < 20, move to left child 10.

2. Step 2: Compare 12 with node 10

   12 > 10, so move to right child 15.

3. Step 3: Compare 12 with node 15

   12 < 15, so move to left child, which is null (not in tree), search ends.

4. Final Answer:

   20 -> 10 -> 15 -> Option A

5. Quick Check:

   Visited nodes = 20, 10, 15 [OK]

Hint: Go left if smaller, right if bigger, stop if null [OK]

Common Mistakes:

• Visiting wrong child nodes
• Assuming 12 is in the tree
• Skipping nodes in path