Binary-Trees

Question 1

Consider the following statements:

    I. The smallest element in a max-heap is always at a leaf node.
    II. The second largest element in a max-heap is always a child of the root node.
    III. A max-heap can be constructed from a binary search tree in Θ(n) time.
    IV. A binary search tree can be constructed from a max-heap in Θ(n) time.

Which of the above statements are TRUE?

A
I, II and III
B
II, III and IV
C
I, III and IV
D
I, II and IV
       Data-Structures       Binary-Trees       GATE 2019
Question 1 Explanation: 
i) TRUE: The smallest element in heap is always a leaf node but depends upon the graph, it may be left or right side of the graph.
(ii) TRUE: The second smallest element in a heap is always a child of root node.

(iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.
(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.
Question 2

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.

A
5.54
B
1.34
C
4.25
D
3.82
       Data-Structures       Binary-Trees       GATE 2019
Question 2 Explanation: 
There can be 8 paths between any 2 uniformly & independently chosen leaf nodes.
A node can be chosen twice and the path from that node to itself will be zero.
∴ Path 1 = 0
Similarly,
Path 2 = 2
Path 3 = 4
Path 4 = 4
Path 5 = 6
Path 6 = 6
Path 7 = 6
Path 8 = 6
∴ Expected value = Σ Path length × Probability of selecting path
= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8
= 1/4 + 1/1 + 3/1 + 0
= 4 + 1/4
= 17/4
= 4.25
Question 3

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:

Note: The height of a tree with a single node is 0.
A
4 and 15 respectively
B
3 and 14 respectively
C
4 and 14 respectively
D
3 and 15 respectively
       Engineering-Mathematics       Binary-Trees       GATE 2017 [Set-1]
Question 3 Explanation: 
T be a Binary Search Tree with 15 nodes.
The height of a tree with single node is 0.
Minimum possible height is when it is a complete binary tree.

Maximum possible height is when it is a skewed tree left/right.

So the minimum and maximum possible heights of T are: 3 and 14 respectively.
Question 4

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

A
2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
B
2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
C
7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
D
7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12
       Data-Structures       Binary-Trees       GATE 2017 [Set-2]
Question 4 Explanation: 

From these 2 orders, we can say 12 is the root & 8 is the root of left subtree & 16 is the root of right subtree.

From 2, 6, 7 we can identify 6 is the root from preorder traversal and from 9, 10 → 9 is root.
From <17, 19, 20>, 19 as root.

Hence, 2,7,6,10,9,8 |,15,17,20,19,16 |12 is the post-order traversal.
Question 5

Consider the following New-order strategy for traversing a binary tree:

  • Visit the root;
  • Visit the right subtree using New-order;
  • Visit the left subtree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

A
+ - 1 6 7 * 2 ˆ 5 - 3 4 *
B
- + 1 * 6 7 ˆ 2 - 5 * 3 4
C
- + 1 * 7 6 ˆ 2 - 5 * 4 3
D
1 7 6 * + 2 5 4 3 * - ˆ -
       Data-Structures       Binary-Trees       GATE 2016 [Set-2]
Question 5 Explanation: 
New Order strategy: Root, Right, Left.
Given Reverse Polish Notation as:
3 4 * 5 - 2 ^ 6 7 * 1 + -
We know Reverse Polish Notation takes Left, Right, Root.

So the expression tree looks like

From the tree, we can write the New Order traversal as: Root, Right, Left.
- + 1 * 7 6 ^ 2 - 5 * 4 3
Question 6

A binary tree T has 20 leaves. The number of nodes in T having two children is _________.

A
19
B
20
C
21
D
22
       Data-Structures       Binary-Trees       GATE 2015 [Set-2]
Question 6 Explanation: 
Let the number of vertices of a binary tree with "p" leaves be n then the tree has
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e., root of T) of degree 2
(iii) 'n - p - 1' (i.e., interval) vertices of degree 3
(iv) n - 1 edges
∴ By Handshaking theorem,
p × 1 + 1 × 2 + (n - p - 1) × 3 = 2(n - 1)
⇒n = 2p - 1
= 39 as p = 20
∴ n - p = 19 vertices have exactly two children
Question 7

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____.

A
199
B
198
C
197
D
196
       Data-Structures       Binary-Trees       GATE 2015 [Set-3]
Question 7 Explanation: 
A binary tree T with n leaf nodes have exactly (n - 1) nodes that have exactly two children.
Question 8

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are

A
B1: (1+height(n→right))
B2: (1+max(h1,h2))
B
B1: (height(n→right))
B2: (1+max(h1,h2))
C
B1: height(n→right)
B2: max(h1,h2)
D
B1: (1+ height(n→right))
B2: max(h1,h2)
       Data-Structures       Binary-Trees       GATE 2012
Question 8 Explanation: 

Now, we analyze the code,
The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.
In such case, height of n will be the height of the right subtree + 1.
The box B2 gets executed when both left & right subtrees of n are not NULL.
In such case, height of n will be max of heights of left & right subtrees of n+1.
Question 9

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

A
0
B
1
C
n!
D
       Data-Structures       Binary-Trees       GATE 2011
Question 9 Explanation: 
Corresponding to each set only 1 binary search tree can be formed because in-order is fixed. only 1 tree possible. If Binary trees would be asked n! possible corresponding to each distinct tree set. Here tree structure is fixed and have only 1 possibility for BST as elements are distinct.
Question 10

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

A
0
B
1
C
(n-1)/2
D
n-1
       Data-Structures       Binary-Trees       GATE 2010
Question 10 Explanation: 
Given a Binary Tree with n nodes.
Every node has an odd number of descendants.
Also given every node is considered to be its own descendant.

― This is even number of descendants (2), because A is also considered as a descendant.

― This is odd number of descendants (3), A, B, C are descendants here.
Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.
Question 11

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

A
2h−1
B
2h−1 – 1
C
2h+1– 1
D
2h+1
       Data-Structures       Binary-Trees       GATE 2007
Question 11 Explanation: 
img src = "https://solutionsadda.in/wp-content/uploads/2020/01/f3-4.jpg">
1, 3, 7, 15, 31, ... = 2h+1 - 1
Question 12

The maximum number of binary trees that can be formed with three unlabeled nodes is:

A
1
B
5
C
4
D
3
       Data-Structures       Binary-Trees       GATE 2007
Question 12 Explanation: 
Total number of binary trees possible for n nodes is C(n) = (2n)!/(n+1)!n! C(n) = (2(3))!/(3+1)!3! = 6×5×4×3×2×1/4×3×2×1×3×2 = 5
Total no. of possible trees is 5.

Total = 5
Question 13

The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

A
d e b f g c a
B
e d b g f c a
C
e d b f g c a
D
d e f g b c a
       Data-Structures       Binary-Trees       GATE 2007
Question 13 Explanation: 
Inorder: Left root Right
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g

Pre order: a b d e c f g
Post order: d e b f g c a
Question 14

Consider the following C program segment where CellNode represents a node in a binary tree:

  struct CellNode {
      struct CellNOde *leftChild;
        int element;
      struct CellNode *rightChild;
  };
 
  int GetValue(struct CellNode *ptr) {
      int value = 0;
      if (ptr != NULL)            {
        if ((ptr->leftChild == NULL) &&
              (ptr->rightChild == NULL))
           value = 1;
  else
           value = value + GetValue(ptr->leftChild)
                         + GetValue(ptr->rightChild);
    }
    return(value);
  }

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

A
the number of nodes in the tree
B
the number of internal nodes in the tree
C
the number of leaf nodes in the tree
D
the height of the tree
       Data-Structures       Binary-Trees       GATE 2007
Question 14 Explanation: 
Let take example,

So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.
Question 15

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.

A
log2n
B
n
C
2n+1
D
2n-1
       Data-Structures       Binary-Trees       GATE 2006
Question 15 Explanation: 
The binary right skewed tree follows 2n -1 because level 2 value is 7 and level 3 value 15.
Note: Assume level numbers are start with 0.
Question 16

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

(i) preorder and postorder     (ii) inorder and postorder
(iii) preorder and inorder     (iv) level order and postorder 
A
(i) only
B
(ii), (iii)
C
(iii) only
D
(iv) only
       Data-Structures       Binary-Trees       GATE 2004
Question 16 Explanation: 
→ We have some combinations such that which can be able to identity a tree
(i) Inorder and Preorder
(ii) Inorder and Postorder
(iii) Inorder and Levelorder
→ And following are do not
(i) Post order and Preorder
(ii) Pre order and Level order
(iii) Post order and Level order
Question 17

Consider the following C program segment

struct CellNode
{
  struct CelINode *leftchild;
  int element;
  struct CelINode *rightChild;
}
 
int Dosomething(struct CelINode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}

The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

A
The number of leaf nodes in the tree
B
The number of nodes in the tree
C
The number of internal nodes in the tree
D
The height of the tree
       Data-Structures       Binary-Trees       GATE 2004
Question 17 Explanation: 
→ Dosomething ( ) returns the max (height of left child + 1, height right child + 1).
→ So given that pointer to root of tree is passed to DoSomething ( ), it will return height of the tree. It is done when the height of single node is '0'.
Question 18

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

A
Theory Explanation is given below.
       Data-Structures       Binary-Trees       GATE 2002
Question 18 Explanation: 

Total 5 binary trees are possible with the preorder C, B, A.
Question 19

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

A
(1 2 (4 5 6 7))
B
(1 (2 3 4) 5 6) 7)
C
(1 (2 3 4) (5 6 7))
D
(1 (2 3 NULL) (4 5))
       Data-Structures       Binary-Trees       GATE 2000
Question 19 Explanation: 
Option C:

(Proper Representation)
Question 20

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

A
LASTIN = LASTPOST
B
LASTIN = LASTPRE
C
LASTPRE = LASTPOST
D
None of the above
       Data-Structures       Binary-Trees       GATE 2000
Question 20 Explanation: 
In full Binary tree LASTIN = LASTPRE.
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.
Question 21

Which of the following statements is false?

A
A tree with a n nodes has (n – 1) edges
B
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results
C
A complete binary tree with n internal nodes has (n + 1) leaves
D
Both B and C
       Data-Structures       Binary-Trees       GATE 1998
Question 21 Explanation: 
A: Tree with n nodes must have (n-1) edges.
D: The maximum no. of nodes in a binary tree of height h is 2h+1 - 1.
h=2 ⇒ 23 - 1 ⇒ 7
Question 22

A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

A
5 3 1 2 4 7 8 6
B
5 3 1 2 6 4 8 7
C
5 3 2 4 1 6 7 8
D
5 3 1 2 4 7 6 8
       Data-Structures       Binary-Trees       GATE 1997
Question 22 Explanation: 
Preorder traversal means (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.
Question 23

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?

A
1
B
3
C
7
D
8
       Data-Structures       Binary-Trees       GATE 1996
Question 23 Explanation: 

a, b, c are going to unbalance.
Question 24

Which of the following sequences denotes the post order traversal sequence of the tree of question 14?

A
f e g c d b a
B
g c b d a f e
C
g c d b f e a
D
f e d g c b a
       Data-Structures       Binary-Trees       GATE 1996
Question 24 Explanation: 
Postorder:-
Left → Right → Root
g c d b f e a
Question 25

A binary search tree is generated by inserting in order the following integers:

 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24  

The number of nodes in the left subtree and right subtree of the root respectively is

A
(4, 7)
B
(7, 4)
C
(8, 3)
D
(3, 8)
       Data-Structures       Binary-Trees       GATE 1996
Question 25 Explanation: 
50 is the root node in BST.
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).
Question 26

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.

Which one of the following is the postorder traversal of the tree?

A
20, 19, 18, 16, 15, 12, 11, 10
B
11, 12, 10, 16, 19, 18, 20, 15
C
10, 11, 12, 15, 16, 18, 19, 20
D
19, 16, 18, 20, 11, 12, 10, 15
       Data-Structures       Binary-Trees       GATE 2020
Question 26 Explanation: 


Postorder:
11, 12, 10, 16, 19, 18, 20, 15
Question 27

What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?

A
θ(n4)
B
θ(n2)
C
θ(n3)
D
θ(n2 log n)
       Data-Structures       Binary-Trees       GATE 2020
Question 27 Explanation: 
AVL Tree all operations(insert, delete and search) will take O(logn) time.
In question they asked about n2 elements.
So, In worst case it will take o(n2 log n) time.
Question 28

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.

A
θ(n log k)
B
θ(log n + k)
C
θ(k log n)
D
θ(log n)
       Data-Structures       Binary-Trees       GATE 2020
Question 28 Explanation: 
The idea is to traverse the given binary search tree starting from root. For every node being visited, check if this node lies in range, if yes, then add 1 to result and recur for both of its children. If the current node is smaller than the low value of range, then recur for right child, else recur for left child.
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is log n, hence O(log n+k).
Question 29
 

The weighted external path length of the binary tree in figure is _____

A
144
       Algorithms       Binary-Trees       GATE 1991
Question 29 Explanation: 
Question 30

Choose the correct alternatives (More than one may be correct). The number of rooted binary trees with n nodes is,

A
Equal to the number of ways of multiplying (n+1) matrices.
B
Equal to the number of ways of arranging n out of 2n distinct elements.
C
D
Equal to n!
E
Both (A) and (C).
       Data-Structures       Binary-Trees       GATE 1990
Question 30 Explanation: 
No. of rooted binary trees (unlabeled) with n nodes is given by nth catalan number which equals (2nCn)/(n+1)
Here, both options A and C are true as option A corresponds to n multiply operations of (n+1) matrices, the no. of ways for this is again given by the nth catalan number.
Question 31

Choose the correct alternatives (More than one may be correct).

The total external path length, EPL, of a binary tree with n external nodes is, EPL = ∑wIw, where Iw is the path length of external node w),
A
≤ n2 always.
B
≥ n log2 n always.
C
Equal to n2 always.
D
O(n) for some special trees.
       Data-Structures       Binary-Trees       GATE 1990
Question 31 Explanation: 
Here the question asked for binary tree.
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
Question 32

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?

A
True
B
False
       Data-Structures       Binary-Trees       GATE 1987
Question 32 Explanation: 
To construct binary tree uniquely we need either inorder and postorder or inorder and preorder.
Question 33

If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.

A
True
B
False
       Data-Structures       Binary-Trees       GATE 1987
Question 33 Explanation: 

In the above binary tree, no. of leaves is 3, which is not the power of 2. Hence the given statement is false.
Question 34

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.

MBCAFHPYK
KAMCBYPFH
MABCKYFPH
Pick the true statement from the following.
A
I and II are preorder and inorder sequences, respectively
B
I and III are preorder and postorder sequences, respectively
C
II is the inorder sequence, but nothing more can be said about the other two sequences
D
II and III are the preorder and inorder sequences, respectively
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 34 Explanation: 
In preorder, root comes at the beginning of the traversal sequence and in post order, root comes at last of the traversal sequence.
So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.
Question 35

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

A
II and III only
B
I and III only
C
III and IV only
D
III only
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 35 Explanation: 
Question 36

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

 I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

Which of the following statements is TRUE?

A
I, II and IV are inorder sequences of three different BSTs
B
I is a preorder sequence of some BST with 439 as the root
C
II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
D
IV is a postorder sequence of some BST with 149 as the root
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 36 Explanation: 
A) Incorrect because I & IV are not in ascending order. (Inorder sequence of BST is in increasing order).
B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.
Question 37

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

 I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

How many distinct BSTs can be constructed with 3 distinct keys?

A
4
B
5
C
6
D
9
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 37 Explanation: 
Formula:
2nCn/n+1 = 6C3/7 = 5
Question 38

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n3 can be expressed as

A
n1 + n2 - 1
B
n1 - 2
C
[((n1 + n2)/2)]
D
n2 - 1
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 38 Explanation: 

n1 = 3
n2 = 1
n3 = 1
So, option (B) satisfies.
Question 39

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

A
2 * n1 – 3
B
n2 + 2 * n1 – 2
C
n3 – n2
D
n2 + n1 – 2
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 39 Explanation: 

n1 = 3
n3 = 1
So, option (A) satisfies.
Question 40

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

A
35
B
64
C
128
D
5040
       Data-Structures       Binary-Trees       GATE 2007-IT
Question 40 Explanation: 
To find 60 in BST then there are two possible set i.e., greater than 60 and smaller than 60.
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 41

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

A
10
B
11
C
12
D
15
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 41 Explanation: 
A node in a binary tree has degree 0, 1, 2.
No. of 1 degree nodes = 5
No. of 2 degree nodes = 10
Total no. of edges = (1*5) + (2*10) = 5 + 20 = 25
So, Total no. of edges = 25 + 1 = 26 (No. of nodes in a tree is 1 more than no. of edges)
Total no. of leaf nodes (node with 0 degree) = 26 - 5 - 10 = 11
Question 42

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

A
{10, 75, 64, 43, 60, 57, 55}
B
{90, 12, 68, 34, 62, 45, 55}
C
{9, 85, 47, 68, 43, 57, 55}
D
{79, 14, 72, 56, 16, 53, 55}
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 42 Explanation: 
In the binary search tree on right side of parent number, the number should be greater than it. But in option C, after 47, 43 appears. So, this is False.
Question 43

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element X[i],i≠0 is?

A
⌊i/2⌋
B
⌈(i-1)/2⌉
C
⌈i/2⌉
D
⌈i/2⌉ - 1
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 43 Explanation: 
If index of array start with 1 then directly divide the ith value by 2 and take floor. If index start with '0' then ⌈i/2⌉ - 1.
Question 44

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

A
O(n)
B
O(log n)
C
O(n log n)
D
O(n log log n)
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 44 Explanation: 
It takes O(log n) to heapify an element of heap.
Question 45

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i ≠ 0, is

A
⌊log2 i⌋
B
⌈log2 (i + 1)⌉
C
⌊log2 (i + 1)⌋
D
⌈log2 i⌉
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 45 Explanation: 
If the root node is at level 0 then the level of element X[i] is ⌊log2 (i + 1)⌋.
Question 46

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/2⌋, ....., 0. The time required to construct a heap in this manner is

A
O(log n)
B
O(n)
C
O(n log log n)
D
O(n log n)
       Algorithms       Binary-Trees       GATE 2004-IT
Question 46 Explanation: 
The above statement is actually algorithm for building a heap of an input array A.
And we know that time complexity for building the heap is O(n).
Question 47
If Tree-1 and Tree-2 are the trees indicated below :

Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?
A
Preorder, Postorder
B
Postorder, Inorder
C
Postorder, Preorder
D
Inorder, Preorder
       Data-Structures       Binary-Trees       ISRO-2018
Question 47 Explanation: 
→ Pre order traverses Root, Left, Right.
→ Post order traverses Left, Right, Root.
→ In-order traverses Left, Root, Right.
Tree-1: Post order: GJIHEFBDCA
Tree-2: In order: GJIHEFBDCA
Question 48
Consider the following tree If the post order traversal gives ab-cd*+ then the label of the nodes 1,2,3,… will be
A
+,-,*,a,b,c,d
B
a,-,b,+,c,*,d
C
a,b,c,d,-,*,+
D
-,a,b,+,*,c,d
       Data-Structures        Binary-Trees       ISRO-2017 May
Question 48 Explanation: 
Step-1: Post order traversals yields from left,right and root.

Step-2: The post order sequence is 4526731. The same we have to take it for above constraint.
Step-3: Then the sequence will be ab–cd*+ because 1= +, 2= -, 3= *, 4= a, 5=b, 6=c and 7=d.
Question 49
A complete binary tree with the property that the value at each node is as least as large as the values at its children is known as
A
binary search tree
B
AVL tree
C
completely balanced tree
D
Heap
       Data-Structures       Binary-trees       ISRO CS 2008
Question 49 Explanation: 
In a Max. Binary Heap, the key value at each node is as least as large as the values at its children. Similarly in Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap.
Question 50
A complete binary tree with n non-leaf nodes contains
A
log2n nodes
B
n+1 nodes
C
2n nodes
D
2n+1 nodes
       Data-Structures       Binary-Trees       ISRO-2016
Question 50 Explanation: 
→ A binary tree where each non-leaf node has exactly two children. The number of leaves is n+1. Total number of nodes is 2n+1.
Note: if two leaves having the same parent are removed from the tree, the number of leaves and non-leaves will decrease by 1 because the parent will be a leaf. That means the difference between them is constant. And for a tree having just one node that difference is 1.
Question 51
A full binary tree with n leaves contains:
A
n nodes
B
log2 n nodes
C
2n-1
D
2n
       Data-Structures       Binary-Trees       ISRO CS 2009
Question 51 Explanation: 
A Binary Tree is full if every node has 0 or 2 children. So, in such case, the binary tree with n leaves contains a total of 2*n-1 nodes.

Question 52
Which of the following number of nodes can form a full binary tree?
A
8
B
15
C
14
D
13
       Data-Structures       Binary-Trees       ISRO CS 2013
Question 52 Explanation: 
A full binary tree is a tree in which every node other than the leaves has two children. In short, a full binary tree with N leaves contains 2N - 1 nodes.

Question 53
How many different trees are there with four nodes A, B, C and D ?
A
30
B
60
C
90
D
None of the above
       Data-Structures       Binary-Trees       ISRO CS 2014
Question 53 Explanation: 
For a given nodes”n” , we can get nn-2 number of different trees
n=4. Here, n is number of nodes.
44-2=16.
Given options are wrong options.
  Note: Correct answer is 16
Question 54
A balance factor in AVL tree is used to check
A
What rotation to make
B
if all childs nodes are at same level
C
when the last rotation occurred
D
if the tree is unbalanced
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 22-07-2017
Question 54 Explanation: 
It is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
Question 55
A full binary tree with n non-leaf nodes contains
A
log​ 2​ n nodes
B
n+1 nodes
C
2n nodes
D
2n+1 nodes
       Data-Structures       Binary-Trees       Nielit Scientist-C 2016 march
Question 55 Explanation: 
● A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children
● In a binary tree - a tree where each non-leaf node has exactly two sons - number of leaves is n+1. Total number of nodes is 2n+1.
Full Binary Tree:

In the above tree,non-leaf nodes are 7 so total nodes are 2x7+1=15
Question 56
traversing a binary tree first root and then left and right subtree called__ traversalt
A
postorder
B
preorder
C
inorder
D
none of these
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 2016 march
Question 56 Explanation: 
In order:​ The left subtree is visited first, then the root and later the right subtree.
Pre order:​ The root node is visited first, then the left subtree and finally the right subtree.
Post order:​ First we traverse the left subtree, then the right subtree and finally the root node.
Question 57
Which of the following need not be a binary tree?
A
Search tree
B
Heap
C
AVL tree
D
B tree
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 4-12-2016
Question 57 Explanation: 
B trees need not be the binary tree. B trees may have more than 2 children. The order of B tree is maximum number of children a node can have.
Question 58
The maximum number of nodes in a binary tree of level k, k>=1 is:
A
2​ k​ +1
B
2​ k-1
C
2​ k​ -1
D
2​ k-1​ -1
       Data-Structures       Binary-Trees       Nielit Scientist-B CS 4-12-2016
Question 58 Explanation: 
The number of nodes is equal to 2​ k​ -1 where k≥1. So the minimum level is 1.
For example

The minimum number of nodes 2​ 2​ -1=3
Question 59

Which of the following data structures is used in level order traversal of a binary tree?

A
Skip list
B
Stack
C
Array
D
Queue
       Data-Structures       Binary-Trees       JT(IT) 2018 PART-B Computer Science
Question 59 Explanation: 
Queue data structures is used in level order traversal of a binary tree.
Example:
Level order traversal of binary tree.
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.
printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
a) print temp_node->data
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node
Note:
Level order traversal of binary tree is time Complexity is O(n) where n is number of nodes in the binary tree.
Question 60
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is
A
2​ h
B
2​ h-1​ -1
C
2​ h+1​ -1
D
2​ h+1
       Data-Structures       Binary-Trees       Nielit Scientific Assistance IT 15-10-2017
Question 60 Explanation: 
● The number of nodes n in a full binary tree, is at least n = 2 h + 1 and at most n = 2 h+1 − 1 , where h is the height of the tree. A tree consisting of only a root node has a height of 0.
● The number of leaf nodes l in a perfect binary tree, is l = ( n + 1 )/2 because the number of non-leaf (a.k.a. internal) nodes

● This means that a perfect binary tree with l leaves has n = 2 l − 1 nodes. ● In a balanced full binary tree, h = ⎡ log 2 (l)⎤ + 1 = ⎡ log 2 ((n + 1 )/2)⎤ + 1 = ⎡ log 2 (n + 1 )⎤
● In a perfect full binary tree, l = 2 h thus n = 2 h+1 − 1
● The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is ( n + 1 ) , where only 1 node exists in bottom-most level to the far left.
●The number of internal nodes in a complete binary tree of n nodes is ⎣ n/2⎦ .
Question 61
The number of possible binary trees with 4 nodes is
A
12
B
13
C
14
D
15
       Data-Structures       Binary-Trees       Nielit Scientific Assistance IT 15-10-2017
Question 61 Explanation: 
There is one binary tree with one node. There are two differently shaped trees with two nodes. There are 14 different (shaped) binary trees with four nodes. These different trees are shown below.
Question 62

In a full binary tree of height 10, the number of nodes with degree 0,1, and 2 will be ____,____ and ____ respectively.

Note: Consider height of a tree as the number of nodes in the longest path from root to any leaf node

A
512, 0, 511
B
512, 1, 510
C
511, 0, 512
D
511, 1, 511
       Data-Structures       Binary-Trees       JT(IT) 2018 PART-B Computer Science
Question 62 Explanation: 
→ Height of the full binary tree 2h -1.
Full binary tree consists of either 0 or 2 childs . So one child to the node is not possible.
The number of nodes with the degree of 1 is 0.
The nodes with degree 0 are leaf nodes, 2h-1 = 29 = 512.
The nodes with degree 2 are internal nodes 2h-1 - 1 = 511.
Question 63

Consider an AVL tree constructed by inserting the elements 18, 10, 5, 3, 27, 7, 35, 43, 32 one by one. Which of the following options give the number of comparisons to search the key value 45 in this AVL tree?

A
5
B
4
C
3
D
2
       Data-Structures       Binary-Trees       JT(IT) 2018 PART-B Computer Science
Question 63 Explanation: 
Question 64
A binary search tree contains the values- 1,2,3,4,5,6,7 and 8. The tree is traverses in preorder and the values are printed out. Which of the following sequences is a valid output?
A
5 3 1 2 4 7 8 6
B
5 3 1 2 6 4 9 7
C
5 3 2 4 1 6 7 8
D
5 3 1 2 4 7 6 8
       Data-Structures       Binary-Trees       Nielit Scientific Assistance CS 15-10-2017
Question 64 Explanation: 
Preorder traversal yields (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.
Question 65
The figure below represents a
A
Binary tree
B
Recursive tree
C
Insert sort
D
Unitary tree
       Data-Structures       Binary-Trees       KVS DEC-2013
Question 65 Explanation: 
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Question 66
An important quantitative measure of the complexity of a binary tree is its__. It also provides a measure of the average depth of all nodes in the tree
A
Average path length
B
Median path length
C
Mode path length
D
Simple deviation path length
       Data-Structures       Binary-Trees       KVS DEC-2013
Question 66 Explanation: 
The number of decisions or, alternatively, the number of branches traversed, in reaching a node is called the path length or path to the node.
Question 67
For the following binary tree, in operate the traversal yields the expression
A
-+*/abdef
B
a+bd*-ef/
C
abdef*/+-
D
a+b*d-e/f
       Data-Structures       Binary-Trees       KVS DEC-2017
Question 67 Explanation: 
Here, inoperate the traversal yields the expression means INORDER.
Inorder→ left,root and right.
a+b*d-c/f
Question 68
A full binary tree with height h has _____ nodes.(Assume leaves at h=0)
A
2h-1
B
2h+1
C
2h+1-1
D
2h+1+1
       Data-Structures       Binary-Trees       KVS 30-12-2018 Part B
Question 68 Explanation: 
→A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.
→The height of the binary tree is the longest path from root node to any leaf node in the tree
Question 69
Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be
A
(n/2) -1
B
(n/2) +1
C
(n–1) / 2
D
(n+1) / 2
       Data-Structures       Binary-Trees       UGC NET CS 2016 July- paper-2
Question 69 Explanation: 
→ They are given definition of full binary tree. The full binary tree each node has exactly either zero or two children.
→ The maximum height of the tree will be (n–1) / 2. It is standard property of full binary tree.
Question 70
The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The post-order Traversal is __________.
A
dbefacg
B
debfagc
C
dbefcga
D
debfgca
       Data-Structures       Binary-Trees       UGC NET CS 2015 Jun- paper-2
Question 70 Explanation: 
Inorder: Left root Right
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g

Pre order: a b d e c f g
Post order: d e b f g c a
Question 71
What item is at the root after the following sequence of insertions into an empty splay tree :
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?
A
1
B
2
C
4
D
8
       Data-Structures       Binary-Trees       UGC NET CS 2004 Dec-Paper-2
Question 71 Explanation: 
A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown.



Question 72
Which traversal techniques lists the nodes of a binary search tree in ascending order ?
A
post – order
B
in - order
C
pre - order
D
linear - order
       Data-Structures       Binary-Trees       UGC NET CS 2005 Dec-Paper-2
Question 72 Explanation: 
Inorder traversal technique in binary search tree will always produce ascending order.
Example:

In this traversal method, the left subtree is visited first, then the root and later the right subtree. We should always remember that every node may represent a subtree itself.
Question 73
In the balanced binary tree given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g” ?
A
1
B
3
C
7
D
8
       Data-Structures       Binary-Trees       UGC NET CS 2005 june-paper-2
Question 73 Explanation: 

a, c, d are going to unbalance.
Question 74
Binary search tree is an example of :
A
Divide and conquer technique
B
Greedy algorithm
C
Back tracking
D
Dynamic Programming
       Data-Structures       Binary-Trees       UGC NET CS 2006 Dec-paper-2
Question 74 Explanation: 
Binary search tree is an example of divide and conquer technique.
Procedure:
1. Divide: select lower or upper half
2. Conquer: search selected half
3. Combine: None
Recurrence relation​ : T(n)=T(n/2)+Θ(1)
Using masters theorem,
a=1, b=2, k=0,p=0
T(n)=Θ(logn)
Question 75
In the balanced binary tree given below, how many nodes will become unbalanced when a node is inserted as a child of the node ​ ”g”.
A
1
B
3
C
7
D
8
       Data-Structures       Binary-Trees       UGC NET CS 2006 June-Paper-2
Question 75 Explanation: 

a, c, d are going to unbalance.
Question 76
A full binary tree with n leaves contains
A
n nodes
B
log​ 2​ n nodes
C
2n –1 nodes
D
2​ n​ nodes
       Data-Structures       Binary-Trees       UGC NET CS 2014 Dec-Paper-2
Question 76 Explanation: 
A Binary Tree is full if every node has 0 or 2 children. So, in such case, the binary tree with n leaves contains a total of 2*n-1 nodes.

There are 4 leaf nodes in the above tree.
So, total number of nodes are 2*4-1
=8-1
=7
Question 77
A text is made up of the characters α,β,γ,δ and σ with the probability 0.12, 0.40, 0.15, 0.08 and 0.25 respectively. The optimal coding technique will have the average length of
A
1.7
B
2.15
C
3.4
D
3.8
       Data-Structures       Binary-Trees       UGC NET CS 2014 June-paper-2
Question 77 Explanation: 
Step-1: Sort in descending order according to their probabilities.

Step-2: Perform optimal merge pattern
0.40, 0.25, 0.15, 0.12, 0.08

Step-4: Multiply with length of the code
= (0.40*1) + (0.25*2) + (0.15*3) + (0.12*4) + (0.08*4)
= 2.15
Question 78
The minimum number of nodes in a binary tree of depth d (root is at level 0) is
A
2d – 1
B
2d + 1 – 1
C
d + 1
D
d
       Data-Structures       Binary-Trees       UGC NET CS 2013 Sep-paper-2
Question 78 Explanation: 
Binary tree is a tree where each node has at most 2 children nodes.
Properties:
→The number of nodes at depth d in a perfect binary tree = 2d
→A perfect binary tree of height h has 2h+1 -1 nodes
→Number of leaf nodes in a perfect binary tree of height h = 2h
→Number of internal nodes in a perfect binary tree of height h = 2h -1
→The minimum number of nodes in a binary tree of height h = h+1
→The maximum number of nodes in a binary tree of height h = 2h+1 -1
Question 79
Consider the In-order and Post-order traversals of a tree as given below :
In-order : j e n k o p b f a c l g m d h I
Post-order : j n o p k e f b c l m g h i d a
The Pre-order traversal of the tree shall be
A
a b f e j k n o p c d g l m h i
B
a b c d e f j k n o p g l m h i
C
a b e j k n o p f c d g l m h i
D
j e n o p k f b c l m g h i d a
E
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2013 Sep-paper-2
Question 79 Explanation: 
Step-1: Post order traversal is Left, Right and Root according to post order we are dividing into in-order list.

Step-2:

Step-3: Final tree is

Step-4: Preorder traversal is Root,left and right
preorder= a b e j k n p o f d g l c m i h
Note: Given options are wrong. Excluded for evaluation.
Question 80
The worst case time complexity of AVL tree is better in comparison to binary search tree for
A
Search and Insert Operations
B
Search and Delete Operations
C
Insert and Delete Operations
D
Search, Insert and Delete Operations
       Data-Structures       Binary-Trees       UGC NET CS 2012 Dec-Paper-2
Question 80 Explanation: 
AVL tree is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.

Question 81
In which tree, for every node the height of its left subtree and right subtree differ almost by one ?
A
Binary search tree
B
AVL tree
C
Threaded Binary Tree
D
Complete Binary Tree
       Data-Structures       Binary-Trees       UGC NET CS 2012 Dec-Paper-2
Question 81 Explanation: 
→ AVL tree is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
→ ALV tree
Question 82
Consider the tree given below

Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree.
A
d & h
B
c & k
C
g, b, c, h, i, m
D
c & h
       Data-Structures       Binary-Trees       UGC NET CS 2012 Dec-Paper-2
Question 82 Explanation: 

Eccentricity of a vertex u, is
E(u) = maxu∈v(G) d(u, v)
i.e., the maximum distance of a node to other nodes is the eccentricity of that node

Radius: The minimum eccentricity from all the vertices is considered as the radius of the Graph G denoted by r(G).
Here radius of the graph, r(G)=3
Center:- If the eccentricity of a graph is equal to its radius, then it is known as the central point of the graph.
And in above graph vertex "h" and " c" have eccentricity equal to the radius of the graph. So vertex h and c are the center of graph.
Hence correct answer is option (D).
Question 83
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
A
ABFCDE
B
ADBFEC
C
ABDECF
D
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2012 June-Paper2
Question 83 Explanation: 
Post order traversal tree is look like

Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 84
A binary search tree is a binary tree :
A
All items in the left subtree are less than root
B
All items in the right subtree are greater than or equal to the root
C
Each subtree is itself a binary search tree
D
All of the above
       Data-Structures       Binary-Trees       UGC NET CS 2012 June-Paper2
Question 84 Explanation: 
Binary search tree properties: 1. All items in the left subtree are less than root
2. All items in the right subtree are greater than or equal to the root
3. Each subtree is itself a binary search tree
Question 85
To represent hierarchical relationship between elements, which data structure is suitable ?
A
Dequeue
B
Priority
C
Tree
D
All of the above
       Data-Structures       Binary-Trees       UGC NET CS 2012 June-Paper2
Question 85 Explanation: 
Double-Ended Queue is a data structure in which insertion and deletion of data takes place from different ends. The insertion of data takes place from REAR end and deletion of data takes place from FRONT end. It follows FIFO( First In First Out) order for implementation.

Priority Queue is like a regular queue or stack data structure, but here each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Tree: A tree is a data structure containing a collection of nodes. Here a node can have any number of children. A node with no child is called as leaf node and a node with 1 or more child is called parent node. Each parent node have a pointer to its children.

Question 86
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
A
ABFCDE
B
ADBFEC
C
ABDECF
D
ABDCEF
       Data-Structures       Binary-Trees       UGC NET CS 2011 Dec-Paper-2
Question 86 Explanation: 
Post order traversal tree is look like

Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 87
The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to
A
20 + 21 + ….. 2h
B
20 + 21 + ….. 2h – 1
C
20 + 21 + ….. 2h + 1
D
21 + ….. 2h + 1
       Data-Structures       Binary-Trees       UGC NET CS 2011 Dec-Paper-2
Question 87 Explanation: 
The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to 20 + 21 + ….. 2h. because every phase we are getting 2h.
Suppose, in level-3, it have 23=8 nodes.
Question 88
The number of different trees with 8 nodes is
A
256
B
255
C
248
D
None of these
       Data-Structures       Binary-Trees       UGC NET CS 2011 June-Paper-2
Question 88 Explanation: 
Given data
-- nodes=8
-- Total number of trees=?
Possibility-1: To find total number of trees using nn-2.
= 88-2
= 262144 trees are possible.
Possibility-2: According to given problem, they are using binary tree based on below formula
= 2n -n

= 28 -8
= 248
Note: They are not given proper input.
Question 89
Given a binary tree whose inorder and preorder traversal are given by
In order : E I C F B G D J H K
Preorder : B C E I F D G H J K
The post order traversal of the above binary tree is
A
I E F C G J K H D B
B
I E F C J G K H D B
C
I E F C G K J H D B
D
I E F C G J K D B H
       Data-Structures       Binary-Trees       UGC NET CS 2011 June-Paper-2
Question 89 Explanation: 

Question 90
Consider the problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets. The number of extension cords required is
A
4
B
5
C
6
D
7
       Engineering-Mathematics       Binary-Trees       UGC NET CS 2010 Dec-Paper-2
Question 91
A binary tree with 27 nodes has _______ null branches.
A
54
B
27
C
26
D
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2010 Dec-Paper-2
Question 92
In a complete binary tree of n nodes, how far are the two most distant nodes? Assume each edge in the path counts as !
A
About log2n
B
About 2 log2n
C
About n log2n
D
About 2n
       Data-Structures       Binary-Trees       UGC NET CS 2010 June-Paper-2
Question 92 Explanation: 
According to binary two most distinct nodes are in
level-1: 1 and 2
level-2: 3 and 6.
[Note: Assume that root starts from level-0]

The height of the binary tree is O(log2n). As per the given constraint, we have to calculate individually of left farthest node and right farthest node height.
=log2n*log2n
=2*log2n or (log2n)2
Question 93
In a full binary tree of height k, there are __________ internal nodes.
A
2k-1
B
2k-1
C
2k
D
2k+1
       Data-Structures       Binary-Trees       UGC NET CS 2009-June-Paper-2
Question 93 Explanation: 
→ In a full binary tree of height k, there are 2k-1 internal nodes.
→ A Binary Tree is full if every node has 0 or 2 children.
→ In a Full Binary, number of leaf nodes is number of internal nodes plus 1
L = I + 1
Where,
L = Number of leaf nodes,
I = Number of internal nodes.
Question 94
A binary tree is said to have heap property if the elements along any path :
A
from leaf to root are non–increasing
B
from leaf to root are non–decreasing
C
from root to leaf are non–decreasing
D
from root to leaf are non–increasing
       Data-Structures       Binary-Trees       UGC NET CS 2009-June-Paper-2
Question 94 Explanation: 
A heap is a complete binary tree. A binary tree is said to have heap property if the elements along any path from root to leaf are non–increasing
Question 95
Which of the following can be the sequence of nodes examined in a binary search tree while searching for key 98 ?
A
100,50,75, 60, 98
B
100, 120, 90, 95, 98
C
200,70,100, 95, 98
D
75, 150, 90, 80, 98
       Data-Structures       Binary-Trees       UGC NET CS 2008-june-Paper-2
Question 95 Explanation: 
Binary search tree will follow some rules
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform


Question 96
The height of a binary tree with ‘n’ nodes, in the worst case is :
A
O(log n)
B
O(n)
C
Ω(n log n)
D
Ω (n2)
       Data-Structures       Binary-Trees       UGC NET CS 2007-Dec-Paper-2
Question 96 Explanation: 
The height of a binary tree with ‘n’ nodes, in the worst case is O(n). Sometimes, it will get left skewed/ right skewed based on given input.

Question 97
The maximum number of nodes in a binary tree of depth 10 :
A
1024
B
210 - 1
C
1000
D
None of the above
       Data-Structures       Binary-Trees       UGC NET CS 2007 June-Paper-2
Question 97 Explanation: 
→ The depth of binary tree starts from 0 but not 1.
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2h+1 -1
= 211 -1
= 2048-1
= 2047

Question 98
Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf. Which of the following is correct for the full binary tree?
A
e = i+n
B
e = i+2n
C
e = 2i+n
D
e = 2n+i
       Data-Structures       Binary-Trees       UGC NET CS 2017 Nov- paper-3
Question 98 Explanation: 
→ A node's path length is the number of links (or branches) required to get back to the root.
→ The root has path length zero and the maximum path length in a tree is called the tree's height.
→ The sum of the path lengths of a tree's internal nodes is called the internal path length and the sum of the path lengths of a tree's external nodes is called the external path length.
External Path Length:

The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path length is 25 (Knuth 1997, pp. 399-400). The internal and external path lengths are related by
E = I + 2n,
where n is the number of internal nodes.
Question 99
The number of different binary trees with 6 nodes is ______.
A
6
B
42
C
132
D
256
       Data-Structures       Binary-Trees       UGC NET CS 2016 July- paper-3
Question 99 Explanation: 
Using catalan formula to find the total number of binary trees is (2n)! / (n! * (n+1)!)

Here, n=6

= (2*6)! / (6! * (6+1)!)

= (12)! / (6! * (7)!)

= 479001600 / (720*5040)

= 132

Question 100
Suppose that we have numbers between 1 and 1,000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined ?
A
925, 221, 912, 245, 899, 259, 363, 364
B
3, 400, 388, 220, 267, 383, 382, 279, 364
C
926, 203, 912, 241, 913, 246, 364
D
3, 253, 402, 399, 331, 345, 398, 364
       Data-Structures       Binary-Trees       UGC NET CS 2016 July- paper-3
Question 100 Explanation: 








Question 101
Consider the following implementation of a binary tree data structure. The operator + denotes list-concatenation. That is, [a,b,c] + [d,e] = [a,b,c,d,e].
struct TreeNode:
int value
TreeNode leftChild
TreeNode rightChild
function preOrder(T):
if T == null:
return []
else:
return [T.value] + preOrder(T.leftChild) + preOrder(T.rightChild)
function inOrder(T):
if T == null:
return []
else:
return inOrder(T.leftChild) + [T.value] + inOrder(T.rightChild)
function postOrder(T):
if T == null:
return []
else:
return postOrder(T.leftChild) + postOrder(T.rightChild) + [T.value]
For some T the functions inOrder(T) and preOrder(T) return the following:
inOrder(T): [12,10,6,9,7,2,15,5,1,13,4,3,8,14,11]
preOrder(T): [5,2,10,12,9,6,7,15,13,1,3,4,14,8,11]
What does postOrder(T) return?
A
[12,6,10,7,15,2,9,1,4,13,8,11,14,3,5]
B
[11,8,14,4,3,1,13,15,7,6,9,12,10,2,5]
C
[11,14,8,3,4,13,1,5,15,2,7,9,6,10,12]
D
[12,6,7,9,10,15,2,1,4,8,11,14,3,13,5]
E
Cannot be uniquely determined from given information.
       Data-Structures       Binary-Trees       TIFR PHD CS & SS 2018
Question 102

The listing of nodes after applying the preorder traversal over the following binary tree is:


A
A,B,D,H,I,E,J,K,C,F,G,L
B
H,D,I,B,J,E,K,A,L,F,C,G
C
H,I,D,J,K,E,B,L,F,G,C,A
D
A,B,D,H,I,E,J,K,C,F,L,G
       Data-Structures       Binary-Trees       CIL Part - B
Question 102 Explanation: 
In the Pre-order traversal , the nodes are traversed in the order “root-left-right”.
So option-D is correct.
Question 103
If T is a binary tree with N nodes, then the number of levels is at least:
A
|log2 (N+1)
B
N-1
C
N
D
[log2 (N+1)]
       Data-Structures       Binary-Trees       CIL Part - B
Question 103 Explanation: 
Question 104

Which of the following statements about the following binary tree is FALSE


A
It is a binary serach tree
B
It is a complete binary tree
C
Nodes ‘J’ and ‘K’ are siblings
D
Node ‘B’ is the ancestor of node ‘J’
       Data-Structures       Binary-Trees       CIL Part - B
Question 104 Explanation: 
A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right.
The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.
Only option A is false
Question 105
If T is a binary tree with number of levels as L, then the number of leaf nodes in the binary tree is at most :
A
2L+1
B
2L
C
2L
D
2L-1
       Data-Structures       Binary-Trees       CIL Part - B
Question 105 Explanation: 
Let T be a binary tree with L levels. Then the number of leaves is at most 2L-1.
Question 106
The minimum height of an AVL tree with n nodes is
A
Ceil (log2 (n+1))
B
1.44 log2n
C
Floor (log2 (n+1))
D
1.64 log2n
       Data-Structures       Binary-Trees       ISRO CS 2020
Question 106 Explanation: 
Minimum: ceil(log2(n+1))
Maximum: floor(1.44*log2(n+2)-.328)
Node: Option B is most appropriate among all.
Question 107
The post order traversal of a binary tree is ACEDBHIGF. The preorder traversal is
A
ABCDEFGHI
B
FBADCEGIH
C
FABCDEGHI
D
ABDCEFGIH
E
None of the above
       Data-Structures       Binary-Trees       ISRO CS 2020
Question 108
If the inorder and preorder sequence of nodes of a binary tree are CABDFEHG and DCBAGEFH respectively, then the post order sequence is
A
ABCDEFGH
B
HFEGABCD
C
ABCFHEGD
D
AFHBECGD
       Data-Structures       Binary-Trees       APPSC-2016-DL-CS
Question 108 Explanation: 
Inorder: CABDFEHG
Preorder: DCBAGEFH

Hence, Post-order of above tree will be: ABCFHEGD. Hence, Post-order of above tree will be: ABCFHEGD.
Question 109

A full binary tree with n leaves contains

A
n nodes
B
log2 n nodes
C
2n - 1 nodes
D
2n nodes
       Data-Structures       Binary-Trees       APPSC-2016-DL-CA
Question 109 Explanation: 
A full binary tree with n leaves contains 2n-1 nodes.
Question 110

The maximum height of a binary tree with 'n' nodes is ____

A
(n+n)
B
(n+1)
C
n
D
(n-1)
       Data-Structures       Binary-Trees       CIL 2020
Question 110 Explanation: 
The maximum height of a binary tree with n nodes is n-1, when the tree is skewed.
Question 111

Consider the following two statements.
1. A binary tree T is full if each node is either a leaf or possesses exactly two child nodes.
2. A binary tree with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.
Which statement is/are TRUE?

A
Only 2
B
Only 1
C
1 and 2
D
Neither 1 nor 2
       Data-Structures       Binary-Trees       CIL 2020
Question 111 Explanation: 
S1 is true. The given definition of full binary tree is correct.
S2 is true. The given definition of complete binary tree is correct.
Question 112

In ____balance factor of a node is the difference between left subtree and right subtree.

A
Red Balck tree
B
B+ Tree
C
AVL tree
D
2-3 Tree
       Data-Structures       Binary-Trees       CIL 2020
Question 112 Explanation: 
For a node in a binary tree, the difference between the heights of its left subtree and right subtree is known as balance factor of the node. In a balanced binary tree the heights of two subtrees of every node never differ by more than 1, and this tree is known as AVL tree.
Question 113

The following is the sequence of insertion in a binary search tree.

45, 65, 35, 40, 33, 70, 60, 75, 69 
How many numbers of nodes in Left Sub Tree(LST) and Right Sub Tree(RST) of root node.

A
LST-6, RST-2
B
LST-5, RST-3
C
LST-3, RST-5
D
LST-2, RST-6
       Data-Structures       Binary-Trees       CIL 2020
Question 113 Explanation: 
The given sequence of numbers is,
45, 65, 35, 40, 33, 70, 60, 75, 69
Now let’s draw binary search tree,

So LST contains 3 nodes and RST contains 5 nodes.
Question 114

Consider the following Inorder and Preorder traversal of a tree

Inorder- D B E F A G H C
Pre Order- A B D E F C G H 
What is the postorder traversal of the same tree?

A
D F E B H C G A
B
D F E B G H C A
C
D F E H B G C A
D
D F E B H G C A
       Data-Structures       Binary-Trees       CIL 2020
Question 114 Explanation: 
Inorder - D B E F A G H C
Preorder - A B D E F C G H
Using the Inorder and Preorder we will get the tree as,

Now traversing the tree, we will get postorder traversal as,
D F E B H G C A
Question 115

Which one from the following is a true statement about Binary trees (BST)?

A
A BST is the Binary tree in which data in the nodes is ordered in a particular way.
B
The data in any nodes of right subtree of BST must be greater than or equal to the data in the given node.
C
A BST have worst case when the data is already in order.
D
All (1), (2) and (3).
       Data-Structures       Binary-Trees       APPSC-2012-DL CA
Question 115 Explanation: 
1. In Binary search tree the right child of a node is greater than or equal to given node and left child of a node is less than the given node. So true.
2. True.
3. True, in this case the tree will be skewed.
Question 116
Depth of a complete binary tree with n nodes is (where log is to the base 2).
A
log (n+1)-1
B
log (n)
C
log (n-1)+1
D
log (n)+1
       Data-Structures       Binary-Trees       TNPSC-2012-Polytechnic-CS
Question 116 Explanation: 
Let's take example,

n=7
So depth is 2.
Now let's check option by option,
A) log(n+1) - 1
log(7+1) - 1
= 3 - 1 = 2
B) log n
log 7
= 2・8
C) log(n-1) + 1
log(7-1) + 1
log 6 + 1 = 2.58 + 1
= 3.58
D) log n + 1
log 7 + 1
= 2・8 + 1 = 3.8
Question 117
How many binary trees are possible with three nodes?
A
3
B
4
C
6
D
5
       Data-Structures       Binary-Trees       TNPSC-2017-Polytechnic-CS
Question 117 Explanation: 
No. of binary trees possible with n nodes is,
(2n)!/n!(n+1)!
So, for n=3,
6!/3!4! = 6×5/3×2 = 5
There are 117 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com
error: Content is protected !!