Why BST enables efficient searching in Data Structures Theory - Quick Recap

Recall & Review

beginner

What does BST stand for in data structures?

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

beginner

How does the BST property help in searching for a value?

Because the left subtree contains smaller values and the right subtree contains larger values, you can decide to go left or right at each node, reducing the search area quickly.

beginner

Why is searching in a BST more efficient than in a linked list?

In a BST, you skip half of the remaining nodes at each step by choosing left or right, while in a linked list you must check nodes one by one.

intermediate

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

The average time complexity is O(log n), meaning the search time grows slowly as the number of nodes increases.

intermediate

What happens to search efficiency if a BST becomes unbalanced?

If the BST becomes unbalanced (like a linked list), search efficiency drops to O(n), meaning you might have to check many nodes one by one.

What property of a BST allows efficient searching?

A Nodes are connected in a circle

B Left child values are smaller, right child values are larger

C All nodes have the same value

D Each node has three children

The BST property that left children are smaller and right children are larger allows quick decisions to go left or right during search.

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

A O(n)

B O(1)

C O(n^2)

D O(log n)

Balanced BSTs allow searching in O(log n) time because each step halves the search space.

If a BST is unbalanced and looks like a linked list, what is the search time complexity?

A O(1)

B O(log n)

C O(n)

D O(n log n)

An unbalanced BST can degrade to O(n) search time, similar to a linked list.

Why is searching in a linked list less efficient than in a BST?

A Because linked lists require checking nodes one by one

B Because linked lists have no order

C Because linked lists have more children per node

D Because linked lists are always sorted

Linked lists require sequential checking of nodes, making search slower than BST's divide-and-conquer approach.

What does each step in searching a BST do?

A Chooses to go left or right based on value comparison

B Checks all nodes at once

C Skips the root node

D Deletes nodes

Each step compares the target value with the current node and decides to go left or right, narrowing the search.

Explain how the structure of a BST helps make searching faster compared to a simple list.

Think about how you decide which way to go at each node.

Describe what happens to search efficiency if a BST becomes unbalanced and why.

Consider what happens if all nodes are on one side.

Practice

1. Why does a Binary Search Tree (BST) enable faster searching compared to a simple list?

easy

A. Because it stores all elements in a single linked list

B. Because it stores data in a random order

C. Because it allows skipping half of the remaining elements at each step

D. Because it uses hashing to find elements instantly

Solution

1. Step 1: Understand BST search process

   A BST compares the search value with the current node and decides to go left or right, effectively skipping half the tree each time.

2. Step 2: Compare with list search

   In a simple list, you check elements one by one, but BST lets you ignore large parts quickly.

3. Final Answer:

   Because it allows skipping half of the remaining elements at each step -> Option C

4. Quick Check:

   BST halves search space each step = faster search [OK]

Hint: BST halves search space each step for speed [OK]

Common Mistakes:

• Thinking BST stores data randomly
• Confusing BST with hashing
• Assuming BST is a linked list

2. Which of the following is the correct property of a Binary Search Tree (BST)?

easy

A. Left child nodes are greater than the parent node

B. Left child nodes are smaller than the parent node

C. Right child nodes are smaller than the parent node

D. All child nodes have the same value as the parent node

Solution

1. Step 1: Recall BST node property

   In a BST, all nodes in the left subtree have values smaller than the parent node.

2. Step 2: Verify options

   Left child nodes are smaller than the parent node correctly states the left child nodes are smaller; others contradict BST rules.

3. Final Answer:

   Left child nodes are smaller than the parent node -> Option B

4. Quick Check:

   BST left < parent = true [OK]

Hint: Left child < parent, right child > parent [OK]

Common Mistakes:

• Mixing up left and right child values
• Assuming children equal parent
• Thinking left child is greater

3. Given the BST below, what is the result of searching for the value 7?

      10
     /  \
    5    15
   / \     \
  3   7     20

medium

A. Found at right child of 5

B. Found at left child of 5

C. Not found in the tree

D. Found at right child of 10

Solution

1. Step 1: Start search at root node 10

   Since 7 is less than 10, move to the left child node 5.

2. Step 2: Compare with node 5

   7 is greater than 5, so move to the right child of 5, which is 7.

3. Final Answer:

   Found at right child of 5 -> Option A

4. Quick Check:

   7 > 5, right child = 7 [OK]

Hint: Compare and move left or right until found [OK]

Common Mistakes:

• Stopping search too early
• Confusing left and right child directions
• Assuming 7 is right child of 10

4. Identify the error in this BST search pseudocode:

function searchBST(node, value):
  if node is null:
    return false
  if value == node.value:
    return true
  if value < node.value:
    return searchBST(node.right, value)
  else:
    return searchBST(node.left, value)

medium

A. It should search left subtree when value is less than node value

B. It should return true when node is null

C. It should compare value with node.left instead of node.value

D. It should always search both left and right subtrees

Solution

1. Step 1: Check direction of subtree search

   When value is less than node value, search should go to the left subtree, not right.

2. Step 2: Identify the incorrect recursive call

   The code incorrectly calls searchBST(node.right, value) for value < node.value, which is wrong.

3. Final Answer:

   It should search left subtree when value is less than node value -> Option A

4. Quick Check:

   Value < node.value -> search left [OK]

Hint: Less than -> left subtree, greater -> right subtree [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Returning true when node is null
• Searching both subtrees unnecessarily

5. Why does a balanced BST provide more efficient searching than an unbalanced BST?

hard

A. Because unbalanced BSTs do not follow BST rules

B. Because unbalanced BSTs store duplicate values

C. Because balanced BSTs use hashing internally

D. Because balanced BSTs minimize the tree height, reducing search steps

Solution

1. Step 1: Understand tree height impact on search

   Search time depends on tree height; shorter height means fewer steps to find a value.

2. Step 2: Compare balanced vs unbalanced BST

   Balanced BSTs keep height minimal (close to log n), while unbalanced BSTs can become like linked lists with height n.

3. Final Answer:

   Because balanced BSTs minimize the tree height, reducing search steps -> Option D

4. Quick Check:

   Balanced BST height low = faster search [OK]

Hint: Balanced tree = shorter height = faster search [OK]

Common Mistakes:

• Thinking unbalanced BSTs store duplicates
• Confusing BST with hashing
• Assuming unbalanced BSTs break BST rules