Why BST Over Plain Binary Tree in DSA Typescript - Quick Recap

Recall & Review

beginner

What is the main difference between a Binary Search Tree (BST) and a plain Binary Tree?

A BST keeps its nodes in a sorted order where left child nodes are smaller and right child nodes are larger than the parent node, while a plain Binary Tree has no such order.

beginner

Why is searching faster in a BST compared to a plain Binary Tree?

Because BST nodes are sorted, you can decide to go left or right at each step, cutting the search space in half, unlike a plain Binary Tree where you may need to check every node.

intermediate

How does the structure of a BST help in insertion and deletion operations?

Insertion and deletion in a BST maintain the sorted order, allowing these operations to be done efficiently by following the tree structure, unlike in a plain Binary Tree where no order is maintained.

intermediate

What is the average time complexity for search, insert, and delete operations in a balanced BST?

The average time complexity is O(log n) for search, insert, and delete because the tree height is kept low, allowing quick traversal.

beginner

Can a plain Binary Tree guarantee O(log n) search time? Why or why not?

No, a plain Binary Tree cannot guarantee O(log n) search time because it does not maintain any order, so you might have to check every node, leading to O(n) time in the worst case.

What property does a Binary Search Tree maintain that a plain Binary Tree does not?

A Nodes have no order

B Each node has exactly two children

C Nodes are sorted so left child < parent < right child

D Nodes are stored in a linked list

A BST keeps nodes sorted so that left child is smaller and right child is larger than the parent.

Why is searching in a BST generally faster than in a plain Binary Tree?

A Because BST nodes are sorted, allowing binary search

B Because BST has fewer nodes

C Because BST uses hashing

D Because BST stores nodes in an array

BST allows binary search by comparing values and choosing left or right subtree.

What is the worst-case time complexity of searching in a plain Binary Tree?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Without order, you may need to check all nodes, leading to O(n) time.

Which operation benefits from the BST property of sorted nodes?

A Insertion

B Deletion

C Searching

D All of the above

Insertion, deletion, and searching all use the sorted property to be efficient.

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

A It becomes O(n)

B It stays O(log n)

C It becomes O(1)

D It becomes O(n log n)

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

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

Think about how order helps you find things faster.

Describe how insertion works differently in a BST compared to a plain Binary Tree.

Insertion in BST follows rules to keep order.