## 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 thenumber of internal nodes in the tree. | |

height of the tree. | |

number of nodes without a right sibling in the tree. | |

number of leaf nodes in the tree. |

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.

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?

10, 20, 15, 23, 25, 35, 42, 39, 30 | |

15, 10, 25, 23, 20, 42, 35, 39, 30 | |

15, 20, 10, 23, 25, 42, 35, 39, 30 | |

15, 10, 23, 25, 20, 35, 42, 39, 30 |

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

p | |

p + 1 | |

n - p | |

n - p + 1 |

Question 3 Explanation:

Total element = n

RST contains elements = p

Root contains = 1 element

1

Root contains the value is n - p.

RST contains elements = p

Root contains = 1 element

1

^{st}contains = n - (p + 1) elementRoot 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:

2 ^{h-1} | |

2 ^{h-1} + 1 | |

2 ^{h} - 1 | |

2 ^{h} |

Question 4 Explanation:

Let's take an example,

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

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

8, 7, 6, 5, 4, 3, 2, 1 | |

1, 2, 3, 4, 8, 7, 6, 5 | |

2, 1, 4, 3, 6, 7, 8, 5 | |

2, 1, 4, 3, 7, 8, 6, 5 |

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

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 |

4, 1, 6, 7, 3, 2, 5, 8 |

Question 6 Explanation:

Inorder traversal is

(Left, Root, Right)

So, the order will be

4, 1, 6, 7, 3, 2, 5, 8

(Left, Root, Right)

So, the order will be

4, 1, 6, 7, 3, 2, 5, 8

There are 6 questions to complete.