Binary Tree and Binary Search Tree
Part 1: Binary Tree
1. Which of the following is not a type of binary tree?
A. Full binary tree
B. Complete binary tree
C. Ternary tree
D. Perfect binary tree
Correct Answer: Ternary tree
2. A binary tree node can have at most how many children?
A. 1
B. 2
C. 3
D. 4
Correct Answer: 2
3. What is the maximum number of nodes at level ‘l’ in a binary tree?
A. l
B. 2^l
C. 2^(l-1)
D. l^2
Correct Answer: 2^l
4. What is the maximum number of nodes in a binary tree of height h?
A. 2^h
B. 2^(h+1)-1
C. 2^(h-1)
D. h^2
Correct Answer: 2^(h+1)-1
5. In a binary tree, the number of leaf nodes is equal to:
A. n+1
B. n
C. n-1
D. none
Correct Answer: n+1
6. Which traversal uses a stack data structure?
A. Inorder
B. Preorder
C. Postorder
D. All of the above
Correct Answer: All of the above
7. Which of the following traversals is not depth-first?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Correct Answer: Level order
8. Which data structure is used in level order traversal?
A. Stack
B. Queue
C. List
D. Array
Correct Answer: Queue
9. A binary tree with n leaf nodes has how many nodes of degree 2?
A. n-1
B. n+1
C. n
D. none
Correct Answer: n-1
10. What is the minimum height of a binary tree with n nodes?
A. log2(n+1)-1
B. n-1
C. n/2
D. log2(n)
Correct Answer: log2(n+1)-1
11. Which traversal prints the left subtree first, then the root, then right subtree?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Correct Answer: Inorder
12. In preorder traversal, root is visited:
A. First
B. Last
C. Middle
D. None
Correct Answer: First
13. In postorder traversal, root is visited:
A. First
B. Last
C. Middle
D. None
Correct Answer: Last
14. Which traversal is useful for expression tree evaluation?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Correct Answer: Postorder
15. Which traversal gives the prefix expression?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Correct Answer: Preorder
16. Which traversal gives the postfix expression?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Correct Answer: Postorder
17. A full binary tree with n internal nodes has how many leaves?
A. n+1
B. 2n
C. n-1
D. n/2
Correct Answer: n+1
18. Which binary tree traversal is non-recursive and uses a queue?
A. Preorder
B. Inorder
C. Postorder
D. Level order
Correct Answer: Level order
19. Which binary tree property is true?
A. Left child > right child
B. Each node has at most 2 children
C. All nodes are equal
D. None
Correct Answer: Each node has at most 2 children
20. In a binary tree, a node with no children is called:
A. Root
B. Leaf
C. Parent
D. Sibling
Correct Answer: Leaf
21. Which of these is true for a complete binary tree?
A. All levels are full except possibly the last
B. All nodes are at same level
C. All nodes have 2 children
D. None
Correct Answer: All levels are full except possibly the last
22. In a binary tree, height of a single node tree is:
A. 0
B. 1
C. 2
D. None
Correct Answer: 0
23. The root of a binary tree has:
A. No children
B. No parent
C. Two parents
D. One parent
Correct Answer: No parent
24. The process of visiting each node in a tree exactly once is called:
A. Traversal
B. Iteration
C. Recursion
D. Conversion
Correct Answer: Traversal
25. In a binary tree, which node has no parent?
A. Leaf node
B. Root node
C. Internal node
D. None
Correct Answer: Root node
26. Which traversal method can reconstruct a binary tree uniquely when combined with
inorder?
A. Preorder
B. Postorder
C. Level order
D. Any of the above
Correct Answer: Preorder
27. If a binary tree has 7 nodes, what is its minimum height?
A. 2
B. 3
C. 4
D. 1
Correct Answer: 2
28. A binary tree with height 0 has how many nodes?
A. 0
B. 1
C. 2
D. 3
Correct Answer: 1
29. Which traversal technique uses recursion naturally?
A. Preorder
B. Postorder
C. Inorder
D. All
Correct Answer: All
30. Which of these is not a binary tree application?
A. Expression parsing
B. Sorting an array
C. Huffman coding
D. Searching
Correct Answer: Sorting an array
31. Binary tree can be represented using:
A. Array
B. Linked list
C. Both
D. None
Correct Answer: Both
32. Which is true for a perfect binary tree?
A. All internal nodes have 2 children
B. All leaves are at same level
C. Both A and B
D. None
Correct Answer: Both A and B
33. In a full binary tree, if number of leaves is L, number of nodes is:
A. 2L-1
B. L+1
C. L^2
D. L-1
Correct Answer: 2L-1
34. Which algorithm is used for level order traversal?
A. DFS
B. BFS
C. Both
D. None
Correct Answer: BFS
35. What is the total number of null pointers in a binary tree with n nodes?
A. n
B. n+1
C. 2n
D. n-1
Correct Answer: n+1
Part 2: Binary Search Tree
36. In a Binary Search Tree, for each node:
A. Left < root < right
B. Left > root > right
C. Left = right
D. None
Correct Answer: Left < root < right
37. The inorder traversal of a BST gives:
A. Descending order
B. Random order
C. Ascending order
D. None
Correct Answer: Ascending order
38. The time complexity to search a key in a balanced BST is:
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Correct Answer: O(log n)
39. Which traversal is useful to print BST in sorted order?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Correct Answer: Inorder
40. What is the worst-case time complexity for searching in an unbalanced BST?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
Correct Answer: O(n)
41. Insertion in BST follows which property?
A. Binary Heap property
B. Binary Search property
C. AVL property
D. None
Correct Answer: Binary Search property
42. In BST, duplicate values are usually:
A. Allowed on left
B. Allowed on right
C. Not allowed
D. Allowed anywhere
Correct Answer: Not allowed
43. Which node in BST has the largest key?
A. Leftmost node
B. Rightmost node
C. Root node
D. Any leaf
Correct Answer: Rightmost node
44. Which traversal helps to find kth smallest element in BST?
A. Preorder
B. Postorder
C. Inorder
D. Level order
Correct Answer: Inorder
45. Deleting a node with two children in BST requires:
A. Replacing with left child
B. Replacing with right child
C. Replacing with inorder successor or predecessor
D. None
Correct Answer: Replacing with inorder successor or predecessor
46. What is the height of a skewed BST with n nodes?
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
Correct Answer: O(n)
47. Which operation on BST takes minimum time in best case?
A. Search
B. Insert
C. Delete
D. All of these
Correct Answer: All of these
48. If preorder traversal of BST is given, we can uniquely construct the BST.
A. True
B. False
Correct Answer: True
49. BST is not suitable for:
A. Dynamic data
B. Static data
C. Both
D. None
Correct Answer: Static data
50. Which traversal is used to copy a BST?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Correct Answer: Preorder
51. The minimum value in BST is found at:
A. Root
B. Leftmost node
C. Rightmost node
D. None
Correct Answer: Leftmost node
52. The maximum value in BST is found at:
A. Root
B. Leftmost node
C. Rightmost node
D. None
Correct Answer: Rightmost node
53. BST operations are efficient when the tree is:
A. Skewed
B. Balanced
C. Empty
D. Random
Correct Answer: Balanced
54. AVL tree is a type of:
A. Binary tree
B. Binary search tree
C. Heap
D. Graph
Correct Answer: Binary search tree
55. Deleting a leaf node in BST affects:
A. Structure
B. Traversal order
C. Neither
D. Both
Correct Answer: Neither
56. Which of the following is not an advantage of BST?
A. Fast search
B. Fast insertion
C. Fast deletion
D. Random access
Correct Answer: Random access
57. Which case gives maximum height of BST?
A. Sorted input
B. Random input
C. Balanced input
D. None
Correct Answer: Sorted input
58. Which node in BST can have maximum two children?
A. Root
B. Internal
C. Any
D. All
Correct Answer: All
59. The average case time complexity for search in BST is:
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
Correct Answer: O(log n)
60. Inorder predecessor of a node is:
A. Maximum node in left subtree
B. Minimum node in right subtree
C. Root
D. None
Correct Answer: Maximum node in left subtree
61. Inorder successor of a node is:
A. Minimum node in right subtree
B. Maximum node in left subtree
C. Root
D. None
Correct Answer: Minimum node in right subtree
62. BST can be represented using:
A. Array
B. Linked list
C. Both
D. None
Correct Answer: Both
63. If all elements are inserted in increasing order, BST becomes:
A. Balanced
B. Skewed right
C. Skewed left
D. Full
Correct Answer: Skewed right
64. If elements inserted are random, BST tends to be:
A. Balanced
B. Skewed
C. Perfect
D. None
Correct Answer: Balanced
65. What is the space complexity of BST traversal?
A. O(h)
B. O(n)
C. O(1)
D. O(n log n)
Correct Answer: O(h)
66. Which algorithm is used to insert in BST?
A. Recursion
B. Iteration
C. Both
D. None
Correct Answer: Both
67. Which of the following is true for BST?
A. Every subtree is BST
B. Only left subtree is BST
C. Only right subtree is BST
D. None
Correct Answer: Every subtree is BST
68. Which traversal helps reconstruct BST uniquely with preorder?
A. Postorder
B. Inorder
C. Level order
D. None
Correct Answer: Inorder
69. Deleting root in BST with two children involves finding:
A. Inorder predecessor/successor
B. Any leaf
C. Middle node
D. Random node
Correct Answer: Inorder predecessor/successor
70. Balanced BST ensures:
A. O(n) search
B. O(log n) search
C. O(1) search
D. O(n^2) search
Correct Answer: O(log n)