The GATE Grind

GATE 2014 CS (CS3) – Question 22

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

In the rooted tree shown, P is the root. In what order are the nodes visited during an in-order traversal?

Diagram for GATE 2014 CS (CS3) question 22
  1. SQPTRWUV
  2. SQPTUWRV
  3. SQPTWUVR
  4. SQPTRUWV

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) SQPTRWUV

Explanation

For the intended general-tree convention, visit the first child, then the node, then the remaining child subtrees left-to-right. Qsubtree givesSQ; visitP; Rsubtree givesTRWUV. The total is **SQPTRWUV,A**. Unlike binary-tree inorder, this convention must be specified for an arbitrary multi-child tree.