Recursive code on trees

ACompressed recap

🧾

Tree questions are answered recursively: decide the NULL base case, compute the answer for the two subtrees, combine with the root. Count, leaves, height (−1 for NULL with edges), sums and maxima are all O(n). Mirroring swaps children at every node and reverses the inorder. Expression trees hold operators inside and operands at leaves; postorder evaluates them and the traversals spell postfix, prefix and infix.

BMerged rule card

4.4 Recursive code on trees: count nodes, leaves, height, mirror, sums; expression trees

• Recursive pattern: P(NULL) base; P(t) from P(left), P(right) and t.
• count = 1 + L + R; leaves = 1 at a leaf else L + R; height = 1 + max(L, R) with −1 for NULL; sum = data + L + R.
• O(n) time, O(height) stack.
• Mirror: swap children at every node; mirrored inorder = reversed inorder.
• Expression tree: operators inside, operands at leaves; postorder evaluates; traversals give postfix/prefix/infix.

CInterleaved GATE-style questions

Q1MCQ2 marksOutput

What does this print?

void mirror(struct tnode *t)
{
    struct tnode *tmp;
    if (t == NULL) return;
    mirror(t->left);
    mirror(t->right);
    tmp = t->left;               /* swap the two children */
    t->left = t->right;
    t->right = tmp;
}
void in(struct tnode *t) { if (!t) return; in(t->left); printf("%d ", t->data); in(t->right); }

int main(void)
{
    struct tnode *root = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL)));
    in(root); printf("\n");
    mirror(root);
    in(root); printf("\n");
    return 0;
}

• (A) 4 2 7 5 1 3 6 then 1 3 6 2 5 7 4
• (B) 6 3 1 5 7 2 4 twice
• (C) the same line twice
• (D) 4 2 7 5 1 3 6 then 6 3 1 5 7 2 4

Q2NAT1 markLeaves

A function returns 1 for a leaf and the sum over the children otherwise. On a perfect binary tree of height 3, what does it return?

Numerical answer: ________

Q3MCQ1 markBase case

For height in the edges convention, height(NULL) should return:

• (A) −1
• (B) 1
• (C) the depth
• (D) 0

Q4NAT2 marksOutput

What is the second number printed?

int f(struct tnode *t)
{
    int a, b;
    if (t == NULL) return 0;
    a = f(t->left);
    b = f(t->right);
    if (t->left != NULL && t->right != NULL) return a + b + 1;
    return a + b;
}
int g(struct tnode *t)
{
    if (t == NULL) return 0;
    return t->data + (g(t->left) > g(t->right) ? g(t->left) : g(t->right));
}

int main(void)
{
    struct tnode *root = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL)));
    printf("%d %d\n", f(root), g(root));
    return 0;
}

Numerical answer: ________

Q5MCQ2 marksExpression

The postorder of an expression tree is a b c * + d -. The expression is:

• (A) a * b + c − d
• (B) a + b * c − d
• (C) a + b * (c − d)
• (D) (a + b) * c − d

Q6MSQ1 markCosts

Which are O(n) for a binary tree with n nodes?

• (A) finding the maximum key
• (B) mirroring
• (C) computing the height
• (D) counting nodes

Q7NAT2 marksRecursion

A function returns 0 for NULL and 1 + f(left) + f(right) only when the node has exactly one child, else f(left) + f(right). On the example tree (1; 2, 3; 4, 5 under 2; 7 under 5; 6 under 3), what does it return?

Numerical answer: ________

Q8MCQ1 markStack depth

The recursion depth of a height function on a skewed tree of n nodes is about:

• (A) log n
• (B) n²
• (C) n
• (D) 1

DAnswer Vault