Which one of the following is not a linear data structure ?
2009
Which one of the following is not a linear data structure ?
Answer: B. Binary Tree — Concept. A data structure is classified as linear or non-linear by the way its elements are logically connected. It is linear when all the elements lie in one…
- A.
Array
- B.
Binary Tree
- C.
Queue
- D.
Stack
Attempted by 605 students.
Show answer & explanation
Correct answer: B
Concept. A data structure is classified as linear or non-linear by the way its elements are logically connected. It is linear when all the elements lie in one single sequence: every element except the two at the ends has exactly one element immediately before it and exactly one immediately after it, so the structure itself fixes a unique next element at every position. It is non-linear when an element may be connected to more than one successor, so no unique next element is defined and the elements spread across levels or branches.
Applying the test. Ask, for each offered structure, how many immediate successors one element can have. One successor means a single chain, which is linear; two or more means branching, which is non-linear.
Data structure | How its elements are connected | Class |
|---|---|---|
Array | Elements occupy consecutive index positions 0 to n-1; each element has one predecessor and one successor | Linear |
Stack | One sequence in which insertion and deletion both happen at the top end | Linear |
Queue | One sequence in which insertion happens at the rear and deletion at the front | Linear |
Binary Tree | Each node carries up to two child links, so one node can have two immediate successors at the next level | Non-linear |
Cross-check. At each element, ask whether the structure itself fixes a unique next element. In an Array it is the entry at the following index, in a Stack the entry immediately below the top, in a Queue the entry immediately behind. In a Binary Tree a node with two children has no single next node, because the left child and the right child are equally its successors; an order has to be imposed from outside by choosing a traversal scheme such as inorder, preorder, postorder or level-order. That absence of a unique successor, and not any difficulty in visiting the nodes, is what places a binary tree outside the linear family.
Hence, among the four structures offered, the Binary Tree is the one that is not linear. Note that a tree is still stored in memory linearly (an array or a set of nodes); the classification is about the logical relationship between elements, not about their physical storage.