Advanced and K-ary Trees MCQs: 12 Solved Questions with Explanations

K-ary tree questions can look like unrelated formula tests, but four structural checks do most of the work. Parent indices decide heap validity, E=V-1 drives full k-ary counting, null pointers define threading, and separator keys define B-tree nodes. Choose an option and write one line of working before checking each explanation. Coding & DSA is the broader learning route.

1. The four rules to write before attempting the MCQs

Keep these relationships beside you:

• A tree with V vertices has V-1 edges.

• For a full k-ary tree with I internal nodes, kI=V-1, so L=(k-1)I+1.

• In a 0-based k-ary heap, parent(i)=floor((i-1)/k). Its children occupy ki+1 through ki+k.

• A B-tree node with K children has K-1 separator keys.

For a full 4-ary tree with I = 6, internal nodes contribute 4 x 6 = 24 edges. Thus V = 25 and L = 25 - 6 = 19. Directly, (4 - 1) x 6 + 1 = 19.

In these questions, “complete” means the full k-ary condition in which every internal node has exactly k children. Follow each given definition, not another textbook convention.

2. 3-ary heap MCQs 1-2: array validity and insertion

Question 1 (GATE 2006)

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

• A. 1, 3, 5, 6, 8, 9

• B. 9, 6, 3, 1, 8, 5

• C. 9, 3, 6, 8, 5, 1

• D. 9, 5, 6, 8, 3, 1

Answer: D. Check parents, not sorting. 9 dominates 5, 6, 8; 5 dominates 3, 1. B has 6 < 8, C has 3 < 5, and A fails at root.

Question 2 (GATE 2006)

A 3-ary max heap is like a binary max heap, but each node can have up to 3 children. In a 0-based array representation, the root is stored at a[0], the next level is stored from a[1] to a[3], and the following level starts from a[4]. The current valid 3-ary max heap is [9, 5, 6, 8, 3, 1] . An item x is inserted by placing it at a[n] and pushing it up until the max-heap property is satisfied. Suppose the elements 7, 2, 10 and 4 are inserted in that order. Which sequence represents the resultant heap array?

• A. 10, 7, 9, 8, 3, 1, 5, 2, 6, 4

• B. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

• C. 10, 9, 4, 5, 7, 6, 8, 2, 1, 3

• D. 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Answer: A. At index 6, 7 swaps with 5: [9,7,6,8,3,1,5]; 2 stays at 7. From index 8, 10 swaps with 6, then 9: [10,7,9,8,3,1,5,2,6]. The 4 stays at 9 under 9.

For binary-heap delete-max, bottom-up heapify and top-k questions, use Heaps and Priority Queues MCQs: 12 Solved Questions with Explanations. Here, Q1-Q2 isolate 0-based 3-ary parent indices and insertion.

3. Full k-ary tree MCQs 3-6: leaves, internal nodes and branching factor

Question 3 (GATE 2002)

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

• A. n/2

• B. (n - 1)/3

• C. (n - 1)/2

• D. (2n + 1)/3

Answer: D. Since 3I=n-1, I=(n-1)/3. Therefore L=n-I=(2n+1)/3. At n=10, I=3 and L=7.

Question 4 (GATE 1998)

A complete n-ary tree is one in which every node has either 0 or n children. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

• A. x(n - 1) + 1

• B. xn - 1

• C. xn + 1

• D. x(n + 1)

Answer: A. The x internal nodes create nx edges and nx+1 vertices. Thus L=nx+1-x=x(n-1)+1. At n=3, x=4: 13 vertices, 9 leaves.

Question 5 (UGC NET July 2018)

A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left (Leaf) nodes in such a tree with 8 internal nodes will be :

• A. 30

• B. 33

• C. 45

• D. 125

Answer: B. L=(5-1)x8+1=33. Check: 5x8=40 edges give 41 vertices and 41-8=33 leaves.

Question 6 (GATE 2007, UGC NET 2020)

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

• A. 3

• B. 4

• C. 5

• D. 6

Answer: C. 41=10(n-1)+1, so 40=10(n-1), n-1=4 and n=5. Independently, 10 internal nodes create 50 edges, hence 51 vertices and 41 leaves.

For wider study, use GATE Guidance by Sanchit Sir. Need a fundamentals reset? Read Binary Trees and Binary Search Trees.

4. Structural MCQs 7-9: maximum height, asymptotic ratio and mixed degrees

Question 7 (UGC NET June 2016)

Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be

• A. $\frac n 2 - 1$

• B. $\frac n 2 + 1$

• C. $(n - 1) / 2$

• D. $(n + 1) / 2$

Answer: C. Since L=I+1, n=2I+1 and I=(n-1)/2. Chaining internal nodes makes height in edges equal I. At n=7, three internal nodes give height 3.

Question 8 (ISRO 2020)

Of the following, which best approximates the ratio of the number of non-terminal nodes in the total number of nodes in a complete K-ary tree of depth N ?

• A. 1/N

• B. (N-1)/N

• C. 1/K

• D. (K-1)/K

Answer: C. Internal and total counts are (K^N-1)/(K-1) and (K^(N+1)-1)/(K-1). Their ratio tends to 1/K. At K=3, N=4, it is 40/121, close to 1/3.

Question 9 (UGC NET December 2018)

In a ternary tree, the number of internal nodes of degree 1,2, and 3 is 4,3, and 3 respectively. The number of leaf nodes in the ternary tree is

• A. 9

• B. 10

• C. 11

• D. 12

Answer: B. Here degree means children. Internal nodes create 4x1+3x2+3x3=19 edges, hence 20 vertices and 10 leaves. Also, L=1+4x0+3x1+3x2=10.

5. Advanced tree MCQs 10-12: threads, B-tree separators and degree suppression

Question 10 (Bihar STET 2025)

A threaded binary tree is a binary tree in which:

• A. Each node has two children

• B. Each node has at most one child

• C. Each node is connected to its parent

• D. Each node has a thread connecting it to its predecessor or successor

Answer: D. Null child pointers can thread to the inorder predecessor, successor or both. This enables traversal without a stack or parent pointers. A to C are not requirements.

Question 11 (ISRO 2015)

If a node has K children in Btree, then the node contains exactly _____ keys.

• A. K²

• B. K - 1

• C. K + 1

• D. K¹⁄²

Answer: B. Keys separate child ranges: two children need one key, three need two, so K need K-1. At K=5, four keys separate five subtrees.

Question 12 (GATE 2008, Information Technology)

A binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors.

Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

• A. 2 * n₁ - 3

• B. n₂ + 2 * n₁ - 2

• C. n₃ - n₂

• D. n₂ + n₁ - 2

Answer: A. From n₁+2n₂+3n₃=2(n-1) and n=n₁+n₂+n₃, obtain n₃=n₁-2. Suppression preserves degree-1 and degree-3 vertices. Final edges are n₁+n₃-1=2n₁-3. At n₁=3, n₃=1, the reduced four-vertex star has three edges.

6. Six advanced-tree traps and the correct checks

Q12 has a separate invariant: graph-theoretic degree counts neighbours, not children. Joining the neighbours of a removed degree-2 vertex preserves the tree and leaf count.

Tag each miss as index formula, edge count, definition, or algebra. Redo tagged questions after one day, then the full set after one week.

7. Where to go after these 12 advanced-tree MCQs

The short version is simple: use parent indices for heaps, edge counts for k-ary leaf questions, given definitions for height and degree, and separator counts for B-trees. Without looking back, reproduce the Q2 final heap, the Q6 branching factor and the Q12 invariant. Explain each in one line to check that the method, not just the option, stayed with you. Then try Construct a Binary Tree from Traversals as another worked tree exercise. For a structured, implementation-oriented route, continue with DSA using Java.