Tree Traversals

Question 1
A
number of internal nodes in the tree.
B
height of the tree.
C
number of nodes without a right sibling in the tree.
D
number of leaf nodes in the tree.
       Algorithms       Tree Traversals       Gate 2014 Set -03
Question 1 Explanation: 
The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered. ⇒ The function returns the number of leaf nodes in the tree.
Question 2
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
A
10, 20, 15, 23, 25, 35, 42, 39, 30
B
15, 10, 25, 23, 20, 42, 35, 39, 30
C
15, 20, 10, 23, 25, 42, 35, 39, 30
D
15, 10, 23, 25, 20, 35, 42, 39, 30
       Algorithms       Tree Traversals       Gate 2013
Question 2 Explanation: 

From the data,

The Postorder traversal sequence is:
→ 15, 10, 23, 25, 20, 35, 42, 39, 30.
Question 3
The numbers 1, 2, .... n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be
A
p
B
p + 1
C
n - p
D
n - p + 1
       Algorithms       Tree Traversals       Gate 2005-IT
Question 3 Explanation: 
Total element = n
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element

Root contains the value is n - p.
Question 4

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:

A
2h-1
B
2h-1 + 1
C
2h - 1
D
2h
       Algorithms       Tree Traversals       Gate 2005-IT
Question 4 Explanation: 
Let's take an example,

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 5

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be

A
8, 7, 6, 5, 4, 3, 2, 1
B
1, 2, 3, 4, 8, 7, 6, 5
C
2, 1, 4, 3, 6, 7, 8, 5
D
2, 1, 4, 3, 7, 8, 6, 5
       Algorithms       Tree Traversals       Gate 2005-IT
Question 5 Explanation: 
Pre-order is given as
5, 3, 1, 2, 4, 6, 8, 7
In-order is the sorted sequence, i.e.,
1, 2, 3, 4, 5, 6, 7, 8
And we know that with given inorder and preorder, we can draw a unique BST.
So, the BST will be,

Hence, postorder traversasl sequence is,
2, 1, 4, 3, 7, 8, 6, 5
Question 6
 
A
4, 1, 6, 7, 3, 2, 5, 8
       Algorithms       Tree Traversals       Gate-1991
Question 6 Explanation: 
Inorder traversal is
(Left, Root, Right)
So, the order will be
4, 1, 6, 7, 3, 2, 5, 8
There are 6 questions to complete.