Searching in BST in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does searching work in a Binary Search Tree?

Imagine you want to find a number in a Binary Search Tree (BST). What is the main idea behind the search process?

A Randomly pick nodes and check if the number matches until found.

B Start at any leaf and move upwards comparing values until the number is found.

C Start at the root, compare the number, then go left if smaller or right if larger, repeating until found or no child exists.

D Search all nodes in the tree one by one from left to right until the number is found.

💡 Hint

Think about how the BST organizes values to help find numbers quickly.

In a BST, each node's left child has smaller values and the right child has larger values. This lets you decide which path to take at each step, making the search efficient.

📋 Factual

intermediate

What is the worst-case time complexity of searching in a BST?

Consider a Binary Search Tree with n nodes. What is the worst-case time complexity to search for a value?

A O(n), when the tree is skewed like a linked list.

B O(log n), always regardless of tree shape.

C O(1), because BSTs allow instant access.

D O(n log n), due to repeated comparisons.

💡 Hint

Think about what happens if the tree is not balanced.

If the BST is unbalanced and looks like a linked list, you may have to check every node, making the search take O(n) time.

🚀 Application

advanced

Find the node in the BST after searching for 15

Given the BST below, what node will the search end on when looking for the value 15?

Tree structure (each node: value):

• Root: 10
• Left child of 10: 5
• Right child of 10: 20
• Left child of 20: 15
• Right child of 20: 25

A Node with value 20

B Node with value 15

C Node with value 10

D Node with value 25

💡 Hint

Follow the BST search steps comparing 15 with each node value.

Start at 10, 15 is greater so go right to 20. Then 15 is less than 20, go left to 15. Found the node with value 15.

🔍 Analysis

advanced

What happens if you search for a value not in the BST?

Consider searching for the value 13 in the BST below:

• Root: 10
• Left child of 10: 5
• Right child of 10: 20
• Left child of 20: 15
• Right child of 20: 25

What is the result of the search?

A The search loops infinitely because 13 is not found.

B The search returns the root node 10 as the closest value.

C The search returns the node with value 15 as the closest match.

D The search ends at a leaf node where the value would be if it existed, confirming 13 is not in the tree.

💡 Hint

Think about how the search moves down the tree and what happens when it can't go further.

Searching for 13 goes 10 -> 20 -> 15. Since 13 is less than 15, the search tries to go left but finds no child, so it stops, confirming 13 is not present.

❓ Reasoning

expert

How does tree balance affect search efficiency in BST?

Why does balancing a BST improve the efficiency of searching compared to an unbalanced BST?

A Balancing keeps the tree height low, making the maximum search steps close to log(n), speeding up search.

B Balancing increases the number of nodes, so searching takes longer.

C Balancing removes nodes, so fewer values can be searched.

D Balancing changes the node values to be sorted in a list, not a tree.

💡 Hint

Consider how the height of the tree relates to the number of steps in searching.

A balanced BST keeps its height minimal, about log(n), so searching requires fewer steps compared to a tall, unbalanced tree that can have height n.