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.