GATE CS 1996 Q1.14 — Trees

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?