Tree-traversal
Question 1 |
Which one of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, respectively?
 | |
 | |
 | |
 |
Question 1 Explanation:
Inorder traversal is,
Left root right.
Preorder traversal is,
Root left right.
Left root right.
Preorder traversal is,
Root left right.
Question 2 |
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 2 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.
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element
Root contains the value is n - p.
Question 3 |
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:
2h-1 | |
2h-1 + 1 | |
2h - 1 | |
2h |
Question 3 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.
There are 3 questions to complete.