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

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a special type of binary tree where each node's left child has a smaller value, and the right child has a larger value than the node itself.

beginner

Why is searching faster in a BST compared to a plain binary tree?

Because BST keeps nodes in order, it allows skipping half of the tree at each step, making search faster than checking every node in a plain binary tree.

intermediate

What is the average time complexity of search in a BST?

The average time complexity is O(log n), where n is the number of nodes, because the tree is divided roughly in half at each step.

beginner

What is a major drawback of a plain binary tree for searching?

A plain binary tree has no order, so searching may require checking every node, resulting in O(n) time complexity.

intermediate

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

BST structure keeps data ordered, so insertion and deletion can be done efficiently by following the tree's order rules, usually in O(log n) time.

What property distinguishes a BST from a plain binary tree?

A All nodes have the same value

B Each node has exactly two children

C Left child is smaller, right child is larger

D Nodes are arranged randomly

BSTs keep nodes ordered so left child is smaller and right child is larger.

What is the worst-case time complexity for searching in a plain binary tree?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Without order, searching may require checking all nodes, which is O(n).

Why is searching in a BST usually faster than in a plain binary tree?

A Because BSTs are balanced by default

B Because BSTs use hashing

C Because BSTs have fewer nodes

D Because BSTs store data in order allowing skipping half the nodes

BSTs keep data ordered, so search can skip large parts of the tree.

Which operation benefits from the BST property?

A All of the above

B Insertion

C Searching

D Deletion

BST property helps searching, insertion, and deletion by keeping data ordered.

What happens if a BST becomes unbalanced?

A Search time degrades to O(n)

B Search time improves

C Insertion becomes impossible

D Tree becomes a plain binary tree

An unbalanced BST can behave like 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 find data faster.

Describe how the structure of a BST affects insertion and deletion operations compared to a plain binary tree.

Consider how order guides where to add or remove nodes.