Binary Search Tree (BST)

Question 1

What is the worst-case time complexity of searching in a BST?

Accepted Answer

O(n) — In the worst case (a skewed tree / linked list), you may have to traverse every node, making it O(n).

Question 2

What defines the binary-search-tree property?

Accepted Answer

Left smaller, right larger — The BST invariant: left subtree < node < right subtree, recursively. This ordering enables searching by comparison at each node.

Question 3

What is the time complexity of search/insert/delete in a BST of height h?

Accepted Answer

O(h): O(log n) if balanced, O(n) if skewed — Operations follow a root-to-leaf path of length h. A balanced tree has h = O(log n); a degenerate (linked-list-like) tree has h = O(n).

Question 4

An IN-ORDER traversal of a BST produces the keys in…

Accepted Answer

Sorted — Visiting left, node, right respects the BST ordering, so in-order traversal yields keys in ascending sorted order — O(n).

Question 5

What causes a BST to degenerate into an O(n) 'skewed' tree?

Accepted Answer

Inserting already-sorted keys — Inserting sorted data makes each new key the rightmost (or leftmost), producing a linked-list-shaped tree of height n — why self-balancing trees exist.

Question 6

Deleting a node with TWO children in a BST is handled by…

Accepted Answer

Replacing with in-order successor — The in-order successor (smallest key in the right subtree) preserves the BST property when it replaces the deleted node; it has at most one child, so removing it is simple.

Question 7

Self-balancing BSTs like AVL and red-black trees guarantee height of…

Accepted Answer

A height of O(log n) after each rebalance — They use rotations on insert/delete to keep height O(log n), guaranteeing O(log n) operations regardless of insertion order.

Question 8

The in-order SUCCESSOR of a node (with a right subtree) is…

Accepted Answer

The leftmost node in its right subtree — The next-larger key is the minimum of the right subtree — found by going right once, then left until null.

Question 9

Compared to a hash map, a BST's advantage is…

Accepted Answer

Ordered range/successor ops — Hash maps are O(1) but unordered. A balanced BST gives O(log n) operations plus sorted traversal and range/nearest-key queries.

Question 10

To find the k-th smallest element efficiently in a BST, you can…

Accepted Answer

Augment nodes with subtree sizes — Storing each subtree's node count lets you decide left/right by rank in O(h); an in-order traversal also works in O(k) without augmentation.

Binary Search Tree

Binary Search Tree Structure

In-order traversal

Test your knowledge

What is the worst-case time complexity of searching in a BST?

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?