Trees · Data Structures · GATE CSE

Which one of the following sequences when stored in an array at locations $$A[1],....,A[10]$$ forms a max-heap?

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary h...

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from...

Consider the following statements. S1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S2 : The sequenc...

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

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?

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

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. 3, 5, 7, 8, 15, 19, 25 II. 5, 8, 9, 12, 10, 15, 25 II...

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

While inserting the elements $$71, 65, 84, 69, 67, 83$$ in an empty binary search tree $$(BST)$$ in the sequence shown, the element in the lowest leve...

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

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

Consider a complete binary tree where the left and the right sub-trees of the root are max-heaps. The lower bound for the number of operations to conv...

Consider the following rooted tree with the vertex labelled P as the root The order in which the nodes are visited during an in-order traversal of th...

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having ...

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

Which of the following is TRUE?

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:

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

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

The numbers 1, 2, ........, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p node...

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary sear...

Level order traversal of a rooted tree can be done by starting from the root and performing

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses th...

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

Which of the following statements is false?

In the balanced binary tree in Fig. given below, 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 previous question?

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

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

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

You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty ...

Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying array) of the maximum element stored in the heap. T...

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation EXTRACT-MAX(A) ex...

Consider the C function foo and the binary tree shown. typedef struct node { int val; struct node *left, *right; } node; int foo(node *p) { ...

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

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the...

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

Consider the following $$New-order$$ strategy for traversing a binary tree: $$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit the root; $$\,\,\,\,\,\,\, \...

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

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the...

Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftM...

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order. int ProcessArray(int *listA, ...

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie b...

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

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

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

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

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

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

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

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to determine the unique binary searc...

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves ...

Consider the following C program segment where CellNode represents a node in a binary tree: struct CellNode { struct CellNOde *leftChild; ...

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

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:

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

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

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

Which of the following sequences of array elements forms a heap?

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

Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one ...

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is ...

How many distinct binary search trees can be created out of 4 distinct keys?

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the...

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Tw...

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

Consider the following C program segment struct CellNode{ struct CellNode *leftChild; int element; struct CellNode *rightChild; }; ...

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of com...

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tre...

A complete n-ary tree is one in which every node has O or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves ...

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

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

A binary search tree is used to locate the number 43. Which of the following probe sequences are not possible?

If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______ ...