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) _____.

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

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:

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 binary tree T has 20 leaves. The number of nodes in T having two children is _________.

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

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

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?

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?

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:

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

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:

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 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.

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 

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

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

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?

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?

Which of the following statements is false?

Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:

 Inorder       a f b c d g e
 Postorder     a f c g e d b 

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?

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”?

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

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

What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A, B, C? Draw all these binary trees.

A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, the nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1.
Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.

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?

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

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.

Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has 2 descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

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

Consider the binary tree in Figure:

(a) What structure is represented by the binary tree?
(b) Give the different steps for deleting the node with key 5 so that the structure is preserved.
(c) Outline a procedure in pseudo-code to delete an arbitrary node from such a binary tree with n nodes that preserves the structure. What is the worst-case time-complexity of your procedure?

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