Trees MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 20, 2024

What is a tree in data structures?
A) A linear data structure
B) A non-linear data structure
C) A type of array
D) A fixed-size data structure
Answer: B) A non-linear data structure

What is the maximum number of children a binary tree node can have?
A) One
B) Two
C) Three
D) Unlimited
Answer: B) Two

What is the height of a tree?
A) The number of nodes
B) The number of edges from the root to the farthest leaf
C) The total number of levels
D) The number of leaf nodes
Answer: B) The number of edges from the root to the farthest leaf

In a binary tree, what is the maximum number of nodes at level n?
A) n
B) 2^n
C) 2^(n-1)
D) n^2
Answer: B) 2^n

What is a full binary tree?
A) A tree with all levels fully filled
B) A tree where every node has either 0 or 2 children
C) A tree with a single path from root to leaf
D) A tree with at least one leaf node
Answer: B) A tree where every node has either 0 or 2 children

What is a complete binary tree?
A) A tree where all nodes have two children
B) A tree where all levels are fully filled except possibly the last
C) A tree with no leaf nodes
D) A binary tree with only one path
Answer: B) A tree where all levels are fully filled except possibly the last

What is the purpose of a binary search tree (BST)?
A) To store data in a non-linear format
B) To allow efficient searching, insertion, and deletion
C) To keep elements sorted
D) All of the above
Answer: D) All of the above

What is the in-order traversal of a binary tree?
A) Visit the root, then left subtree, then right subtree
B) Visit the left subtree, then root, then right subtree
C) Visit the right subtree, then root, then left subtree
D) Visit nodes in level order
Answer: B) Visit the left subtree, then root, then right subtree

What is the pre-order traversal of a binary tree?
A) Visit the left subtree, then root, then right subtree
B) Visit the root, then left subtree, then right subtree
C) Visit the right subtree, then root, then left subtree
D) Visit nodes in level order
Answer: B) Visit the root, then left subtree, then right subtree

What is the post-order traversal of a binary tree?
A) Visit the left subtree, then root, then right subtree
B) Visit the root, then left subtree, then right subtree
C) Visit the left subtree, then right subtree, then root
D) Visit nodes in level order
Answer: C) Visit the left subtree, then right subtree, then root

What is the worst-case time complexity for searching in a binary search tree?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)

Which of the following is NOT a property of a binary search tree?
A) Left subtree nodes are less than the root
B) Right subtree nodes are greater than the root
C) All nodes must have two children
D) Each subtree must also be a binary search tree
Answer: C) All nodes must have two children

What is the minimum height of a binary tree with n nodes?
A) log(n)
B) n
C) log(n + 1)
D) n – 1
Answer: C) log(n + 1)

What is a balanced binary tree?
A) A tree where all leaf nodes are at the same level
B) A tree where the height difference between left and right subtrees is no more than one
C) A tree that is complete
D) A tree where every node has two children
Answer: B) A tree where the height difference between left and right subtrees is no more than one

What is a binary heap?
A) A complete binary tree that satisfies the heap property
B) A type of binary search tree
C) A linear data structure
D) A tree with random node arrangement
Answer: A) A complete binary tree that satisfies the heap property

What is the space complexity for storing a binary tree?
A) O(n)
B) O(log n)
C) O(1)
D) O(n log n)
Answer: A) O(n)

Which traversal method is used to sort a binary search tree?
A) In-order traversal
B) Pre-order traversal
C) Post-order traversal
D) Level-order traversal
Answer: A) In-order traversal

What is the level of a node in a tree?
A) The number of edges from the root to the node
B) The height of the node
C) The total number of nodes
D) The depth of the node
Answer: A) The number of edges from the root to the node

What is a leaf node in a tree?
A) A node with no children
B) A node with one child
C) A node with two children
D) A node that is the root
Answer: A) A node with no children

Which data structure can be used to implement a tree?
A) Array
B) Linked list
C) Both A and B
D) None of the above
Answer: C) Both A and B

What is the breadth-first search (BFS) traversal of a tree?
A) Level-order traversal
B) Pre-order traversal
C) In-order traversal
D) Post-order traversal
Answer: A) Level-order traversal

What is a binary tree with all nodes having 0 or 1 child called?
A) Complete binary tree
B) Full binary tree
C) Degenerate tree
D) Balanced binary tree
Answer: C) Degenerate tree

What is the depth of a node in a tree?
A) The number of nodes from the root to the node
B) The number of edges from the root to the node
C) The height of the tree
D) The level of the tree
Answer: B) The number of edges from the root to the node

What is a B-tree?
A) A binary search tree
B) A self-balancing tree that maintains sorted data
C) A complete binary tree
D) A type of heap
Answer: B) A self-balancing tree that maintains sorted data

What is the height of a balanced binary tree with n nodes?
A) log(n)
B) n
C) n/2
D) log(n + 1)
Answer: A) log(n)

What is a Red-Black tree?
A) A type of binary search tree
B) A self-balancing binary search tree
C) A binary heap
D) A complete binary tree
Answer: B) A self-balancing binary search tree

What is the main advantage of using a self-balancing tree?
A) It requires less memory
B) It maintains a balanced structure for efficient operations
C) It is easier to implement
D) It allows for random access
Answer: B) It maintains a balanced structure for efficient operations

What is a thread in a threaded binary tree?
A) A pointer to the next node in in-order traversal
B) A pointer to the parent node
C) A pointer to a child node
D) A pointer to the root node
Answer: A) A pointer to the next node in in-order traversal

What type of tree is used to implement a priority queue?
A) Binary search tree
B) AVL tree
C) Binary heap
D) Red-Black tree
Answer: C) Binary heap

What is the main characteristic of a ternary tree?
A) Each node has up to three children
B) Each node has up to two children
C) It is a complete binary tree
D) It is a degenerate tree
Answer: A) Each node has up to three children

What type of traversal uses a stack?
A) Breadth-first search
B) Depth-first search
C) In-order traversal
D) Both B and C
Answer: D) Both B and C

What is the primary characteristic of a Splay tree?
A) It is self-balancing
B) It uses rotation to move frequently accessed nodes closer to the root
C) It is a binary search tree
D) All of the above
Answer: D) All of the above

What is the function of the left and right pointers in a binary tree node?
A) To point to the parent node
B) To store data
C) To point to the left and right children
D) To store the height of the tree
Answer: C) To point to the left and right children

In which scenario would you use a trie?
A) To implement a priority queue
B) To store strings for fast retrieval
C) For numerical data storage
D) For tree traversal
Answer: B) To store strings for fast retrieval

What is the main disadvantage of a linked representation of a binary tree?
A) It is less efficient than an array
B) It consumes more memory due to pointers
C) It is harder to implement
D) All of the above
Answer: B) It consumes more memory due to pointers

What is the relationship between the height and number of nodes in a complete binary tree?
A) Height = log(n)
B) Height = n
C) Height = n/2
D) Height = n – 1
Answer: A) Height = log(n)

What does the term “height balanced” refer to in trees?
A) The height is the same for all nodes
B) The difference in heights between left and right subtrees is minimal
C) All levels are completely filled
D) The total number of nodes is minimal
Answer: B) The difference in heights between left and right subtrees is minimal

Which tree structure allows for fast lookup, insertion, and deletion operations?
A) Linked list
B) Array
C) Binary search tree
D) Stack
Answer: C) Binary search tree