List of top Computer Science and IT Engineering Questions on Trees asked in GATE CS

Let 𝑛 be an odd number greater than 100. Consider a binary minheap with
𝑛 elements stored in an array 𝑃 whose index starts from 1.
Which of the following indices of 𝑃 do/does NOT correspond to any leaf node of
the minheap?

Consider a binary search tree (BST) with 𝑛 leaf nodes (𝑛> 0). Given any node 𝑉,
the key present in the node is denoted as π‘‰π‘Žπ‘™(𝑉). All the keys present in the given
BST are distinct. The keys belong to the set of real numbers.
For a node 𝑉, let 𝑆𝑒𝑐(𝑉) denote the node that is its inorder successor. If a node 𝑉
does not have an inorder successor, then 𝑆𝑒𝑐(𝑉) is π‘π‘ˆπΏπΏ. As there are no
duplicates, if 𝑆𝑒𝑐(𝑉) is not π‘π‘ˆπΏπΏ, then π‘‰π‘Žπ‘™(𝑉) < π‘‰π‘Žπ‘™(𝑆𝑒𝑐(𝑉)).
Corresponding to every leaf node 𝐿𝑖 that has a non-NULL 𝑆𝑒𝑐(𝐿𝑖), a new key π‘˜π‘–
with the following property is to be inserted into the BST.
π‘‰π‘Žπ‘™(𝐿𝑖) < π‘˜π‘–< π‘‰π‘Žπ‘™(𝑆𝑒𝑐(𝐿𝑖))
Let 𝐾 represent the list of all such new keys to be inserted into the BST.
Which of the following statements is/are true?

The following sequence corresponds to the preorder traversal of a binary search
tree 𝑇:
50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77
The position of the element 60 in the postorder traversal of 𝑇 is ______. (answer in
integer)
Note: The position begins with 1.

Let 𝑃 be the set of all integers from 1 to 15. Consider any order of insertion of the
elements of 𝑃 into a binary search tree that creates a complete binary tree.
Which one of the following elements can NEVER be the third element that is
inserted?

The height of a binary tree is the number of edges in the longest path from the root
to a leaf in the tree. The maximum possible height of a full binary tree with
23 nodes is _________. (answer in integer)

The set T represents various traversals over binary tree. The set S represents the
order of visiting nodes during a traversal.
T
S
I: Inorder
L: left subtree, node, right subtree
II: Preorder
M: node, left subtree, right subtree
III: Postorder N: left subtree, right subtree, node
Which one of the following is the correct match from T to S ?