Data Structures Trees and Binary Search Trees

Question 1

What is the height of a complete binary tree with n nodes?

Accepted Answer

O(log n)

Answer

A complete binary tree doubles the number of nodes at each level, so its height is floor(log₂ n), which is O(log n).

Question 2

Which tree traversal visits nodes in ascending order for a Binary Search Tree?

Accepted Answer

In-order

Answer

In-order traversal visits left subtree, root, then right subtree; for a BST this produces nodes in sorted ascending order.

Question 3

What property must a Binary Search Tree satisfy at every node?

Accepted Answer

All left descendants < node value < all right descendants

Answer

Every node in a BST must have all values in its left subtree less than the node's value and all values in its right subtree greater.

Question 4

What is the worst-case time complexity of search in an unbalanced BST?

Accepted Answer

O(n)

Answer

An unbalanced BST can degenerate into a linked list (e.g., inserting sorted data), making search O(n) in the worst case.

Question 5

Which self-balancing BST uses red-black coloring to maintain O(log n) operations?

Accepted Answer

Red-Black tree

Answer

Red-Black trees enforce coloring rules that guarantee the tree height stays O(log n), ensuring all operations remain O(log n).

Data Structures Practice Test