C Programming Trees MCQs
Basic Trees in C (30 Questions)
1. What is a tree in data structures?
A) A linear data structure
B) A hierarchical data structure
C) A first-in-first-out structure
D) A last-in-first-out structure
Answer: B) A hierarchical data structure
A tree is a non-linear hierarchical data structure that consists of nodes connected by edges.
2. What is the topmost node in a tree called?
A) Leaf node
B) Root node
C) Internal node
D) Child node
Answer: B) Root node
The root is the topmost node in a tree structure from which all other nodes descend.
3. What is a node with no children called?
A) Root node
B) Internal node
C) Leaf node
D) Parent node
Answer: C) Leaf node
Leaf nodes (or terminal nodes) are nodes without any children in a tree structure.
4. What is the height of a tree?
A) Number of nodes in the tree
B) Number of edges from root to deepest leaf
C) Number of levels in the tree
D) Number of leaf nodes
Answer: B) Number of edges from root to deepest leaf
The height of a tree is defined as the number of edges on the longest path from the root node to a leaf node.
5. Which of the following is NOT a tree traversal method?
A) In-order
B) Pre-order
C) Post-order
D) Random-order
Answer: D) Random-order
The standard tree traversal methods are in-order, pre-order, and post-order.
6. What is the degree of a node in a tree?
A) Its depth in the tree
B) Its height from the leaves
C) Number of its children
D) Number of its ancestors
Answer: C) Number of its children
The degree of a node is the number of children it has in the tree structure.
7. Which of the following is a binary tree property?
A) Each node has exactly two children
B) Each node has at most two children
C) Each node has at least two children
D) Each node has exactly one child
Answer: B) Each node has at most two children
In a binary tree, each node can have 0, 1, or 2 children.
8. What is the time complexity of searching in a balanced binary search tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
In a balanced BST, search operations take logarithmic time as we halve the search space at each step.
9. Which traversal gives nodes in non-decreasing order in a BST?
A) Pre-order
B) In-order
C) Post-order
D) Level-order
Answer: B) In-order
In-order traversal of a BST yields nodes in ascending order.
10. What is the maximum number of nodes at level 'l' in a binary tree?
A) l
B) 2^l
C) 2^(l-1)
D) 2^l - 1
Answer: C) 2^(l-1)
In a binary tree, the maximum number of nodes at level l is 2^(l-1) (root is level 1).
11. What is a complete binary tree?
A) All levels are completely filled
B) All levels except possibly the last are completely filled
C) All nodes have exactly two children
D) All leaf nodes are at the same level
Answer: B) All levels except possibly the last are completely filled
In a complete binary tree, all levels except possibly the last are completely filled and all nodes are as far left as possible.
12. What is the maximum number of nodes in a binary tree of height h?
A) h
B) 2^h
C) 2^(h+1) - 1
D) 2^h - 1
Answer: D) 2^h - 1
A binary tree of height h can have at most 2^h - 1 nodes.
13. Which of the following is true for a binary search tree?
A) Left child is greater than parent
B) Right child is less than parent
C) Left subtree contains only greater values
D) Right subtree contains only greater values
Answer: D) Right subtree contains only greater values
In a BST, all nodes in the right subtree are greater than the parent node.
14. What is the time complexity of inserting a node in a BST?
A) O(1)
B) O(log n) average, O(n) worst
C) O(n)
D) O(n log n)
Answer: B) O(log n) average, O(n) worst
Insertion in BST is O(log n) on average for balanced trees, but O(n) in worst case for skewed trees.
15. What is an AVL tree?
A) A BST with height balance property
B) A BST where all leaf nodes are at same level
C) A BST with maximum height
D) A BST with color property
Answer: A) A BST with height balance property
An AVL tree is a self-balancing BST where the difference between heights of left and right subtrees cannot be more than 1.
16. What is the balance factor of a node in AVL tree?
A) Height of left subtree + height of right subtree
B) Height of left subtree - height of right subtree
C) Number of nodes in left subtree - number of nodes in right subtree
D) Number of leaf nodes in left subtree - number of leaf nodes in right subtree
Answer: B) Height of left subtree - height of right subtree
Balance factor is the difference between heights of left and right subtrees.
17. Which rotation is needed when left-left case occurs in AVL tree?
A) Left rotation
B) Right rotation
C) Left-right rotation
D) Right-left rotation
Answer: B) Right rotation
Left-left case requires a single right rotation to balance the tree.
18. What is a B-tree?
A) A binary search tree
B) A self-balancing tree with multiple keys per node
C) A tree with only two levels
D) A tree where all nodes have exactly two children
Answer: B) A self-balancing tree with multiple keys per node
B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
19. What is the minimum number of keys in a non-root node of a B-tree of order m?
A) m
B) m/2
C) ceil(m/2) - 1
D) m - 1
Answer: C) ceil(m/2) - 1
In a B-tree of order m, each non-root node must have at least ceil(m/2)-1 keys.
20. What is a heap?
A) A complete binary tree with heap property
B) A binary search tree
C) A tree with only one level
D) A tree where all nodes have same value
Answer: A) A complete binary tree with heap property
A heap is a specialized complete binary tree-based data structure that satisfies the heap property.
21. What is the heap property for a max-heap?
A) Parent is greater than or equal to children
B) Parent is less than or equal to children
C) Left child is greater than right child
D) Right child is greater than left child
Answer: A) Parent is greater than or equal to children
In a max-heap, the value of each parent node is greater than or equal to the values of its children.
22. What is the time complexity to build a heap from an array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
Building a heap from an unsorted array can be done in O(n) time using heapify process.
23. What is the time complexity of heap sort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: D) O(n log n)
Heap sort has O(n log n) time complexity for all cases.
24. What is a trie?
A) A binary search tree
B) A tree where each node represents a character
C) A heap data structure
D) A B-tree variant
Answer: B) A tree where each node represents a character
A trie (prefix tree) is a tree-like data structure where each node represents a single character of a string.
25. What is the advantage of a trie?
A) Efficient prefix searches
B) Constant time insertion
C) No memory usage
D) Always balanced
Answer: A) Efficient prefix searches
Tries allow for efficient prefix searches and are useful for autocomplete features and dictionary implementations.
26. What is a segment tree?
A) A tree for storing segments
B) A tree for range queries
C) A binary search tree
D) A heap structure
Answer: B) A tree for range queries
A segment tree is a data structure that allows answering range queries efficiently.
27. What is the time complexity for range sum query in a segment tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Segment trees can answer range queries (like sum, min, max) in O(log n) time.
28. What is a Fenwick tree?
A) Another name for binary search tree
B) A tree for efficient prefix sum calculations
C) A type of heap
D) A balanced binary tree
Answer: B) A tree for efficient prefix sum calculations
A Fenwick tree (or Binary Indexed Tree) is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
29. What is the time complexity for point update in a Fenwick tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Fenwick trees support both point updates and prefix sum queries in O(log n) time.
30. What is a red-black tree?
A) A BST with color property for balancing
B) A tree where all nodes are red
C) A tree where all nodes are black
D) A heap with color coding
Answer: A) A BST with color property for balancing
A red-black tree is a self-balancing binary search tree where each node has an extra bit for color (red or black) to maintain balance.
Tree Algorithms in C (20 Questions)
1. What is the typical node structure for a binary tree in C?
A) struct node { int data; };
B) struct node { int data; struct node *left; struct node *right; };
C) struct node { int data; struct node *child; };
D) struct node { int data; struct node *next; };
Answer: B) struct node { int data; struct node *left; struct node *right; };
A binary tree node typically contains data and pointers to left and right children.
2. Which traversal uses a queue?
A) Pre-order
B) In-order
C) Post-order
D) Level-order
Answer: D) Level-order
Level-order (BFS) traversal uses a queue to visit nodes level by level.
3. What is the correct pre-order traversal for the following tree?
A
/ \
B C
A) A, B, C
B) B, A, C
C) B, C, A
D) C, B, A
Answer: A) A, B, C
Pre-order traversal follows Root-Left-Right order.
4. What is the correct in-order traversal for the following tree?
A
/ \
B C
A) A, B, C
B) B, A, C
C) B, C, A
D) C, B, A
Answer: B) B, A, C
In-order traversal follows Left-Root-Right order.
5. What is the correct post-order traversal for the following tree?
A
/ \
B C
A) A, B, C
B) B, A, C
C) B, C, A
D) C, B, A
Answer: C) B, C, A
Post-order traversal follows Left-Right-Root order.
6. Which traversal would you use to delete a tree?
A) Pre-order
B) In-order
C) Post-order
D) Level-order
Answer: C) Post-order
Post-order traversal is used to delete nodes as it processes children before parent.
7. What is the time complexity of tree traversal algorithms?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
All standard tree traversals visit each node exactly once, so O(n) time.
8. How would you find the height of a binary tree?
A) Count all nodes
B) Recursively find max height of left and right subtrees
C) Count leaf nodes
D) Use level-order traversal
Answer: B) Recursively find max height of left and right subtrees
Height is 1 + maximum of heights of left and right subtrees.
9. What is the time complexity to find the height of a binary tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
Finding height requires visiting all nodes in worst case.
10. How would you check if two binary trees are identical?
A) Compare their heights
B) Compare their traversals
C) Recursively compare nodes and their children
D) Compare root values only
Answer: C) Recursively compare nodes and their children
Two trees are identical if their root values match and left/right subtrees are identical.
11. How would you find the diameter of a binary tree?
A) Maximum height of the tree
B) Longest path between any two nodes
C) Number of nodes in the longest path between two leaves
D) Both B and C
Answer: D) Both B and C
Diameter is the longest path between any two nodes (number of edges) or nodes (number of nodes).
12. What is the time complexity to find the diameter of a binary tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
We can find diameter in O(n) time by calculating heights and diameters recursively.
13. How would you check if a binary tree is balanced?
A) Check if left and right subtrees have same height
B) Check if height difference between left and right subtrees is at most 1
C) Check if all leaf nodes are at same level
D) Check if tree is complete
Answer: B) Check if height difference between left and right subtrees is at most 1
A balanced tree has height difference between left and right subtrees no more than 1 for every node.
14. What is the time complexity to check if a binary tree is balanced?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
We need to check all nodes to verify balance condition.
15. How would you find the lowest common ancestor (LCA) of two nodes in a BST?
A) Find node where one target is in left subtree and other in right subtree
B) Find node with value between the two target values
C) Both A and B
D) Use post-order traversal
Answer: C) Both A and B
In BST, LCA is the node where one target is in left and other in right subtree, which is also the node with value between the two targets.
16. What is the time complexity to find LCA in a BST?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
In balanced BST, we can find LCA in O(log n) time by traversing from root.
17. How would you serialize a binary tree?
A) Store node values in pre-order with NULL markers
B) Store node values in level-order
C) Store node values in sorted order
D) Both A and B
Answer: D) Both A and B
Binary trees can be serialized using pre-order (with NULL markers) or level-order traversal.
18. What is the time complexity to serialize a binary tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
Serialization requires visiting all nodes once.
19. How would you implement a level-order traversal?
A) Using recursion
B) Using a queue
C) Using a stack
D) Using an array
Answer: B) Using a queue
Level-order traversal (BFS) is implemented using a queue to process nodes level by level.
20. What is the space complexity of level-order traversal?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
In worst case (complete tree), queue may contain all leaf nodes (n/2 nodes).
Related Tree Resources