Why BST Over Plain Binary Tree in DSA C++ - Quick Recap

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a binary tree where each node's left child has a smaller value and the right child has a larger value than the node itself. This property helps in faster searching.

beginner

How does a BST improve search efficiency compared to a plain binary tree?

BST uses the order property to decide which subtree to search, reducing the search space by half each step, leading to average search time of O(log n) instead of O(n) in plain binary trees.

beginner

Why is a plain binary tree less efficient for search operations?

A plain binary tree has no order property, so to find a value, you may need to check every node, resulting in O(n) time complexity.

beginner

What real-life analogy helps understand why BST is better than a plain binary tree for searching?

Like a phone book sorted by names (BST), you can quickly find a name by skipping half the book each time. A plain list (plain binary tree) requires checking every name one by one.

intermediate

What is the worst-case time complexity of search in a BST and when does it happen?

The worst-case time is O(n), which happens when the BST becomes skewed (like a linked list) due to inserting sorted data without balancing.

What property makes BST faster for searching than a plain binary tree?

A Nodes are arranged in sorted order

B Nodes have more children

C Nodes store extra data

D Nodes are connected randomly

BST nodes are arranged so left child < parent < right child, enabling faster search.

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

A O(n)

B O(n log n)

C O(log n)

D O(1)

Balanced BST reduces search space by half each step, leading to O(log n) time.

In which case does BST search degrade to O(n)?

A When tree has duplicate values

B When tree is empty

C When tree is balanced

D When tree is skewed

A skewed BST behaves like a linked list, causing O(n) search time.

Which data structure is like a phone book for quick searching?

A Plain binary tree

B Binary Search Tree

C Linked list

D Stack

BST is like a sorted phone book allowing quick search.

Why is a plain binary tree not efficient for searching?

A It has no order property

B It has too many nodes

C It uses too much memory

D It is always balanced

Without order, search must check every node, making it slow.

Explain why a Binary Search Tree is preferred over a plain binary tree for searching data.

Think about how sorting helps find things faster.

Describe a real-life example that helps understand the advantage of BST over a plain binary tree.

Imagine looking up a name in a phone book.