## Trees

Question 1 |

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.

1 | |

2 | |

3 | |

4 |

Question 1 Explanation:

Post – 8 9 6 7 4 5 2 3 1
In - 8 6 9 4 7 2 5 1 3
Post: 8 9 6 7 4 5 2 3①⏟root
In: 8 6 9 4 7 2 5⏟left subtree 13⏟right subtree

Question 2 |

Let

*T*be a tree with 10 vertices. The sum of the degrees of all the vertices in*T*is _________.18 | |

19 | |

20 | |

21 |

Question 2 Explanation:

Sum of degrees of all vertices is double the number of edges.

A tree, with 10 vertices, consists n-1, i.e. 10-1 =9 edges.

Sum of degrees of all vertices = 2(#edges)

= 2(9)

= 18.

A tree, with 10 vertices, consists n-1, i.e. 10-1 =9 edges.

Sum of degrees of all vertices = 2(#edges)

= 2(9)

= 18.

Question 3 |

64 | |

65 | |

66 | |

67 |

Question 3 Explanation:

The number of ways in which the number 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6 is:

Given the height of a tree with a single node is 0.

The root must be either 1 or 7, so with 1, 7 we can form 2 ways (left & right skew) each.

For each height we have 2 choices, except the leaf node.

Hence T(n) = 2 * T (n – 1)

∵ Total number of ways will be 2

Given the height of a tree with a single node is 0.

The root must be either 1 or 7, so with 1, 7 we can form 2 ways (left & right skew) each.

For each height we have 2 choices, except the leaf node.

Hence T(n) = 2 * T (n – 1)

∵ Total number of ways will be 2

^{(n-1)}=2^{(7-1)}=2^{6}=64Question 4 |

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

63 and 6, respectively | |

64 and 5, respectively | |

32 and 6, respectively
| |

31 and 5, respectively |

Question 4 Explanation:

Maximum number of nodes in a binary tree of height h is,

2

Minimum number of nodes in a binary tree of height h is

h + 1 = 5 + 1 = 6

2

^{h+1}- 1 = 2^{5+1}- 1 = 63Minimum number of nodes in a binary tree of height h is

h + 1 = 5 + 1 = 6

Question 5 |

None of the above |

Question 5 Explanation:

Given Tree is

Insert G at root level:

Insert G at root level:

Question 6 |

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:

log _{2} n | |

n - 1 | |

n | |

2 ^{n} |

Question 6 Explanation:

A binary tree is a tree data structure in which each node has atmost two child nodes.

The no. of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1 and 2.

The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.

The number of nodes of degree 2 in T is "n - 1".

The no. of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1 and 2.

The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.

The number of nodes of degree 2 in T is "n - 1".

Question 7 |

4 | |

5 | |

6 | |

7 | |

Both A and D |

Question 7 Explanation:

Case 1:

Where L is leaf node.

So, no. of internal node is 4.

Case 2:

Where L is leaf node.

So, no. of internal node is 7.

Where L is leaf node.

So, no. of internal node is 4.

Case 2:

Where L is leaf node.

So, no. of internal node is 7.

There are 7 questions to complete.