GATE CS Trees questions

The set $\mathbf{T}$ represents various traversals over binary tree. The set $\mathbf{S}$ represents the order of visiting nodes during a traversal. …

​​​​Consider a binary tree $T$ in which every node has either zero or two children. Let $n>0$ be the number of nodes in $T$. Which ONE of the following is the number of nodes in $T$ that have exactly two children?

Consider the $\text{C}$ function $\text{foo}$ and the binary tree shown. typedef struct node { int val; struct node *left, *right; } node; int foo(node *p) { int retval; if (p == NULL) return 0; else { retval = p->val + foo(p->left) + foo(p->right); printf("%d ", retval); return retval; } } When $\textsf{foo}$ is called with a pointer to the …

An $articulation$ $point$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a $\text{DFS}$ tree obtained by doing $\text{DFS}$ in a connected undirected graph $G$. Which of the following options is/are correct?

Consider a complete binary tree with $7$ nodes. Let $A$ denote the set of first $3$ elements obtained by performing Breadth-First Search $\text{(BFS)}$ starting from the root. Let $B$ denote the set of first $3$ elements obtained by performing Depth-First Search $\text{(DFS)}$ starting from the root. The value of $\mid A-B \mid$ is …

What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially?

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$ (ie., the number of edges in the unique path between $a$ and $b$) is (rounded off to $2$ decimal …

The postorder traversal of a binary tree is $\text{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 tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _____

Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ 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:

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

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

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 exactly $4$ nodes is $O(n^a\log^bn)$. Then the value of $a+10b$ is __________.

Consider the pseudocode given below. The function $DoSomething()$ takes as argument a pointer to the root of an arbitrary tree represented by the $leftMostChild-rightSibling$ representation. Each node of the tree is of type $treeNode$. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr …

Consider the following rooted tree with the vertex labeled $P$ as the root: The order in which the nodes are visited during an in-order traversal of the tree is

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudo-code below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root. int height(treeptr n) { if(n == NULL) return -1; if(n -> left == NULL) if(n -> right == NULL) return 0; else return B1; // …

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?

Consider the following C program segment where $\text{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 …