## Tree Traversals

 Question 1
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree->leftMostChild == NULL) value = 1; else value = DoSomething(tree->leftMostChild); value = value + DoSomething(tree->rightSibling); } return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
 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.