BST Search Operation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Search for Existing Value

What will be the output of the following TypeScript code that searches for a value in a Binary Search Tree?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(value: number) {
    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;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value: number): boolean {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) current = current.left;
      else current = current.right;
    }
    return false;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

console.log(tree.search(7));

A false

B true

C undefined

D TypeError

💡 Hint

Think about whether the value 7 exists in the tree after insertion.

The value 7 was inserted into the BST. The search method traverses the tree comparing values. Since 7 exists, the method returns true.

❓ Predict Output

intermediate

Output of BST Search for Non-Existing Value

What will be the output of the following TypeScript code that searches for a value not present in the Binary Search Tree?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(value: number) {
    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;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value: number): boolean {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) current = current.left;
      else current = current.right;
    }
    return false;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

console.log(tree.search(8));

A undefined

B true

C false

D ReferenceError

💡 Hint

Check if 8 was inserted into the tree before searching.

The value 8 was never inserted into the BST. The search method traverses the tree but does not find 8, so it returns false.

🧠 Conceptual

advanced

Understanding BST Search Path

In a Binary Search Tree, when searching for the value 12, which path will the search follow given the tree below? Tree structure: - Root: 10 - Left child of 10: 5 - Right child of 10: 15 - Left child of 15: 12 - Right child of 15: 20 Choose the correct sequence of nodes visited during the search for 12.

A 10 -> 12

B 10 -> 5 -> 12

C 10 -> 15 -> 20

D 10 -> 15 -> 12

💡 Hint

Remember that in BST, values less than current node go left, greater go right.

Starting at 10, since 12 > 10, go right to 15. Then 12 < 15, go left to 12. So the path is 10 -> 15 -> 12.

❓ Predict Output

advanced

Output of BST Search with Null Root

What will be the output of the following TypeScript code when searching in an empty Binary Search Tree?

DSA Typescript

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

class BST {
  root: Node | null = null;

  search(value: number): boolean {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) current = current.left;
      else current = current.right;
    }
    return false;
  }
}

const tree = new BST();
console.log(tree.search(5));

A false

B TypeError

C true

D undefined

💡 Hint

The tree is empty, so no nodes exist to find any value.

The root is null, so the search loop never runs and the method returns false.

❓ Predict Output

expert

Output of BST Search After Multiple Insertions and Searches

Consider the following TypeScript code that inserts multiple values into a BST and then searches for several values. What will be the output printed to the console?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(value: number) {
    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;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value: number): boolean {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) current = current.left;
      else current = current.right;
    }
    return false;
  }
}

const tree = new BST();
tree.insert(20);
tree.insert(10);
tree.insert(30);
tree.insert(25);
tree.insert(35);
tree.insert(5);
tree.insert(15);

console.log(tree.search(15));
console.log(tree.search(40));
console.log(tree.search(5));
console.log(tree.search(17));

A

true
false
true
false

B

false
false
true
false

C

true
true
true
false

D

true
false
false
true

💡 Hint

Check each searched value against the inserted values carefully.

Values 15 and 5 were inserted, so search returns true for them. Values 40 and 17 were not inserted, so search returns false for them.