BST Search Operation in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A Binary Search Tree is a tree data structure where each node has at most two children. The left child's value is less than the parent's value, and the right child's value is greater than the parent's value.

beginner

How does the search operation work in a BST?

Start at the root. If the value equals the node's value, return it. If the value is less, search the left subtree. If greater, search the right subtree. Repeat until found or no nodes left.

intermediate

What is the time complexity of searching in a balanced BST?

The time complexity is O(log n) because each step eliminates half of the remaining nodes to search.

beginner

What happens if the value is not found in the BST during search?

The search reaches a null child (no node), meaning the value is not in the tree. The operation returns null or indicates not found.

intermediate

Show the JavaScript code snippet for searching a value in a BST node.

function searchBST(node, val) {
  if (node === null) return null;
  if (node.val === val) return node;
  if (val < node.val) return searchBST(node.left, val);
  else return searchBST(node.right, val);
}

In a BST, where do you search if the target value is less than the current node's value?

A Left subtree

B Right subtree

C Both subtrees

D Root node only

If the target value is less than the current node's value, the search continues in the left subtree.

What is the time complexity of searching in a balanced BST?

A O(n)

B O(1)

C O(n log n)

D O(log n)

In a balanced BST, the search time is O(log n) because the tree halves the search space each step.

What does the search function return if the value is not found in the BST?

A The last visited node

B Null or equivalent

C The root node

D An error

If the value is not found, the search reaches a null child and returns null.

Which property must a BST satisfy for the search operation to work correctly?

A Left child values are less than parent, right child values are greater

B Right child values are less than parent

C All nodes have two children

D Left child values are greater than parent

BST property: left child values < parent, right child values > parent.

What is the first step in the BST search operation?

A Check the left child

B Check the right child

C Compare the target value with the root node's value

D Return null

The search starts by comparing the target value with the root node's value.

Explain how the search operation works in a Binary Search Tree.

Think about how you decide which side of the tree to explore.

Write a simple recursive function in JavaScript to search for a value in a BST.

Use if-else conditions and recursion.