Data Structures Trees and Binary Search Trees 1 — Questions and Answers
Question 1: What is the height of a complete binary tree with n nodes?
- O(n)
- O(log n) (Correct answer)
- O(√n)
- O(n log n)
Correct answer: O(log n)
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?
- Pre-order
- Post-order
- In-order (Correct answer)
- Level-order
Correct answer: In-order
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?
- Left child equals parent value
- All left descendants < node value < all right descendants (Correct answer)
- Left subtree height equals right subtree height
- Node value is greater than all nodes in the tree
Correct answer: All left descendants < node value < all right descendants
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?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n log n)
Correct answer: O(n)
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?
- AVL tree
- Red-Black tree (Correct answer)
- B-tree
- Splay tree
Correct answer: Red-Black tree
Red-Black trees enforce coloring rules that guarantee the tree height stays O(log n), ensuring all operations remain O(log n).
Question 6: What is the lowest common ancestor (LCA) of two nodes in a BST?
- The root of the tree
- The deepest node that is an ancestor of both nodes (Correct answer)
- The parent of the shallower node
- The node with value equal to the average of both nodes
Correct answer: The deepest node that is an ancestor of both nodes
The LCA is the deepest (lowest) node that has both target nodes as descendants, including the nodes themselves.
Data Structures Trees and Binary Search Trees 1
What is the height of a complete binary tree with n nodes?