Non-Linear Data Structures: Trees: 17 MCQs with answers

D · Each node can have many children, giving a one-to-many shape.

Linear structures like arrays and lists are one-to-one; a tree is one-to-many because a node can point to multiple children, which is the defining non-linear property.

D · Leaf

A node with no children is a leaf (degree 0). The root is the topmost node, and a parent is a node with at least one child.

B · 14

Every node except the root has exactly one parent edge, so a tree with $n$ nodes has $n - 1$ edges: $15 - 1 = 14$.

D · Inorder

Inorder visits left subtree, node, then right subtree. Because a BST keeps smaller values on the left and larger on the right, this produces sorted output.

C · A tree

Nested folders form a hierarchy — each folder can contain many items, which is exactly the one-to-many shape of a tree.

A · True

A tree with $n$ nodes always has exactly $n - 1$ edges and contains no cycles.

C · It is the number of children the node has.

Degree counts a node's children. The number of edges from the root is depth, and the maximum depth is the tree's height.

B · It cannot be a tree because it contains at least one cycle.

A tree with $n$ nodes must have exactly $n - 1$ edges. With 10 nodes and 12 edges there are more edges than a tree allows, so at least one cycle exists.

C · It degrades to $O(n)$ because the tree becomes list-like.

Sorted input makes every new node a right child, producing a degenerate linked-list-like tree of height $n$, so search becomes $O(n)$.

D · Postorder, so children are removed before parents.

Postorder processes left and right subtrees before the node, so every child is freed before its parent — the safe order for deletion.

D · A BST enforces left-smaller and right-larger ordering at every node.

Both limit children to two, but only a BST adds the ordering rule that makes fast search possible.

B · A forest

A forest is exactly a set of disjoint trees. A subtree is a node plus its descendants within one tree.

D · Both A and R are true, and R correctly explains A.

Each non-root node contributes exactly one edge to its parent, so edges equal non-root nodes, which is $n - 1$. The reason is the direct justification of the assertion.

A · I and II only

Trees are connected and acyclic, so I and II hold. Statement III is false: graphs may contain cycles or be disconnected, so not every graph is a tree.

D · A self-balancing tree such as an AVL or red-black tree

Sorted insertion degenerates a naive BST to $O(n)$ search. A self-balancing tree keeps height near $\log n$, preserving $O(\log n)$ lookups.

B · It is a graph but not a tree, because it contains a cycle.

A tree must be acyclic. Tracing a loop back to the start proves a cycle exists, so the structure is a general graph, not a tree.

D · 2

The depth of a node in a tree is defined as the number of edges from the root to that node. In this BST, the root is 30 (depth 0), 20 is the left child of 30 (depth 1), and 25 is the right child of 20 (depth 2). Therefore, the depth of the node containing the value 25 is 2.