Q1: Consider the following rooted tree with the vertex labelled P as the root (2014 SET 3)
The order in which the nodes are visited during an in-order traversal of the tree is
(a) SQPTRWUV
(b) SQPTUWRV
(c) SQPTWUVR
(d) SQPTRUWV
Ans: (a)
Sol: The inorder traversal of a ternary tree is given by Left > Root > Middle > Right.
But if you apply this traversal sequence on this tree, the order is SQPTWURV.
According to the answer given by various books, the answer is (A).
(A) can only be the answer if we consider 'S' to be the left child of 'Q', and 'W' to be the left child of 'U'.
Q2: 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? (2007)
(a) 3
(b) 4
(c) 5
(d) 6
Ans: (c)
Sol: If you do little bit experiments on no of leaves, Internal nodes, you will realize that they have equation like following :-
No of leaves (L) = (n - 1)∗ Internal Nodes (I) + 1
Here we need to find n.
Putting values
41 = (n - 1) ∗ 10 + 1
⟹ (n - 1) ∗ 10 = 40
⟹ n - 1 = 4
⟹ n = 5
Q3: In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is: (2005)
(a) nk
(b) (n -1)k + 1
(c) n(k - 1) + 1
(d) n(k -1)
Ans: (c)
Sol:
Originally when we have root , there is only 1 node, which is leaf. (There is no internal node.) From that "+1" part of formula comes from this base case.
When we k children to nodes, we make root internal. So then Total Leaves
= n (k -1) + 1 = (k - 1) + k
In k complete k ary tree every time you add k children , you add k - 1 leaves.(+k for leaves,-1 for node which you are attaching )
Q4: The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is (2002)
(a) n/2
(b) (n-1) /3
(c) (n-1)/2
(d) (2n+1)/3
Ans: (d)
Sol:
L = leaf nodes
I = internal nodes
n = total nodes = L + I
In a tree no. of edges = n - 1
All edges are produced by only internal nodes so,
k × I = n - 1 → ( 1 ) (for k - ary tree, in this question k = 3)
L + I = n → ( 2 )
Here, given options are in terms of "n". So, eliminating I from (1) and (2),
L = ((k - 1)n + 1)/k
you get L = (2n + 1)/3
Answer is D.
Q5: A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by (1998)
(a) x(n-1)+1
(b) xn-1
(c) xn+1
(d) x(n+1)
Ans: (a)
Sol: x (n - 1) + 1
Originally when we have root , there is only 1 node, which is leaf. (There is no internal node.) From this base case "+1" part of formula comes. When we n children to root, we make root internal. So then Total Leaves
= 1(n - 1) + 1 = n .
In complete n ary tree every time you add n children to node, you add n - 1 leaves & make that node to which you are inserting children internal.(+n for leaves,-1 for node which you are attaching ). So if you had originally few leaves, you add n - 1"New" leaves to them. This is how x(n - 1) + 1 makes sense.
