GATE CS Trees questions

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 in a complete $n-ary$ tree. If $L = 41$ and $I = 10$, what is the value of $n$?

The inorder and preorder traversal of a binary tree are $\text{d b e a f c g}$ and $\text{a b d e c f g}$, respectively The postorder traversal of the binary tree is:

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

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

An Abstract Data Type (ADT) is:

Consider the following C program segment struct CellNode{ struct CellNode *leftChild int element; struct CellNode *rightChild; }; int Dosomething (struct CellNode *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 …

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? preorder and postorder inorder and postorder preorder and inorder level order and postorder

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

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

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 tree. Which of the following is always true?

Consider the following nested representation of binary trees: $(X \ Y \ Z)$ indicates $Y$ and $Z$ are the left and right subtrees, 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 complete $n$-ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$-ary tree, the number of leaves in it is given by

Which of the following statements is false?

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

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 binary tree $T$ has $n$ leaf nodes. The number of nodes of degree $2$ in $T$ is

A $2-3$ tree is such that All internal nodes have either $2$ or $3$ children All paths from root to the leaves have the same length The number of internal nodes of a $2-3$ tree having $9$ leaves could be