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

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.

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

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?

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 

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?

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

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.

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.

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.

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?

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

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 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 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 binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n₃ can be expressed as

A binary tree with n > 1 nodes has n₁, n₂ and n₃ 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?

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

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?

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?

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

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

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

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

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

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