## 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 _______.
 A 1 B 2 C 3 D 4
Data-Structures       Trees       Gate 2018
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 1→(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 _________.
 A 18 B 19 C 20 D 21
Data-Structures       Trees       Gate 2017 set-01
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
 Question 3

The number of ways in which the numbers 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 _________.

Note: The height of a tree with a single node is 0.
 A 64 B 65 C 66 D 67
Data-Structures       Trees       GATE 2016 set-2
Question 3 Explanation:
To get the tree of height 6, every level should contain only 1 node.
So to get such tree at each level we should have either maximum or minimum element from remaining numbers till that level. So no. of binary search tree possible is,
1st level - 2 (maximum or minimum)

2nd level - 2

3rd level - 2

4th level - 2

5th level - 2

6th level - 2

7th level - 2
= 2 × 2 × 2 × 2 × 2 × 2 × 1
= 26
= 64
 Question 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
 A 63 and 6, respectively B 64 and 5, respectively C 32 and 6, respectively D 31 and 5, respectively
Data-Structures       Trees       GATE 2015 (Set-01)
Question 4 Explanation:
Maximum number of nodes in a binary tree of height h is,
2h+1 - 1 = 25+1 - 1 = 63
Minimum number of nodes in a binary tree of height h is
h + 1 = 5 + 1 = 6
 Question 5
Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree. What is the result of inserting G in the above tree ?
 A B C D None of the above
Data-Structures       Trees       Gate-2003
Question 5 Explanation:
Given Tree is 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:
 A log2 n B n - 1 C n D 2n
Data-Structures       Trees       Gate-1995
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".
 Question 7
 A 4 B 5 C 6 D 7 E Both A and D
Data-Structures       Trees       Gate-1992
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.
There are 7 questions to complete.