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

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Which pairs of traversals determine a unique binary tree? from Lesson 4.3.3
• What does preorder print first? from Lesson 4.3.1
• How do you find the value of a recursive function without shared variables? from Lesson 2.1.4

1 · The Hook

🎣

A manager asks the head of each department: “how many people work under you?” Each head asks the heads of their sub-departments, adds the answers, and adds one for themselves. Nobody counts the whole company, yet the total arrives at the top. Almost every question about a tree is answered this way: ask the left subtree, ask the right subtree, combine.

2 · Predict First

🤔

For the example tree of this phase, what do these functions return?

int count(struct tnode *t)  { return t == NULL ? 0 : 1 + count(t->left) + count(t->right); }
int leaves(struct tnode *t)
{
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return 1;
    return leaves(t->left) + leaves(t->right);
}
int height(struct tnode *t)                 /* edges; empty tree -1 */
{
    int a, b;
    if (t == NULL) return -1;
    a = height(t->left);
    b = height(t->right);
    return 1 + (a > b ? a : b);
}
int sum(struct tnode *t)    { return t == NULL ? 0 : t->data + sum(t->left) + sum(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 %d %d\n", count(root), leaves(root), height(root), sum(root));
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

7 3 3 28

7 nodes, 3 leaves (4, 7, 6), height 3 (1 → 2 → 5 → 7), sum 1 + … + 7 = 28.

The pattern

For a property P of a tree: P(NULL) is the base case; otherwise compute P of the left and right subtrees recursively and combine them with the root. One call per node: O(n) time, O(height) stack depth.

Classic functions

Mirror (swap left and right everywhere)

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

Output

4 2 7 5 1 3 6 
6 3 1 5 7 2 4

The inorder of the mirror is the reverse of the original inorder.

Expression trees

An expression tree stores an arithmetic expression: operators at internal nodes, operands at leaves; each operator’s subtrees are its operands. Evaluation is a postorder computation; the traversals spell the expression in postfix (postorder), prefix (preorder) and, with brackets added, infix (inorder). From a postfix expression the tree is built with a stack of trees (Lesson 3.2.2’s value stack, holding subtrees instead of numbers).

/* an expression tree: operators in internal nodes (stored as characters), digits at leaves */
struct enode {
    char op;                 /* '+', '-', '*', '/' or 0 for a leaf */
    int val;
    struct enode *l, *r;
};

struct enode *leaf(int v) { struct enode *e = malloc(sizeof *e); e->op = 0; e->val = v; e->l = e->r = NULL; return e; }
struct enode *opn(char op, struct enode *l, struct enode *r) { struct enode *e = malloc(sizeof *e); e->op = op; e->val = 0; e->l = l; e->r = r; return e; }

int eval(struct enode *e)
{
    int a, b;
    if (e->op == 0) return e->val;
    a = eval(e->l);
    b = eval(e->r);
    switch (e->op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        default:  return a / b;
    }
}

void postfix(struct enode *e) { if (!e) return; postfix(e->l); postfix(e->r); if (e->op) printf("%c ", e->op); else printf("%d ", e->val); }
void infix(struct enode *e)
{
    if (e->op == 0) { printf("%d", e->val); return; }
    printf("(");
    infix(e->l);
    printf(" %c ", e->op);
    infix(e->r);
    printf(")");
}

int main(void)
{
    /* (3 + 4) * (5 - 2) */
    struct enode *t = opn('*', opn('+', leaf(3), leaf(4)), opn('-', leaf(5), leaf(2)));
    postfix(t); printf("\n");
    infix(t);   printf(" = %d\n", eval(t));
    return 0;
}

Output

3 4 + 5 2 - * 
((3 + 4) * (5 - 2)) = 21

4 · Visual

Heights (edges) computed bottom-up: leaves 0, then 1 + the taller child.

Expression tree of (3 + 4) * (5 − 2) = 21.

height(1) = 1 + max(height(2), height(3))
          = 1 + max( 1 + max(h(4), h(5)) ,  1 + max(-1, h(6)) )
          = 1 + max( 1 + max(0, 1)       ,  1 + max(-1, 0)   )
          = 1 + max( 2, 1 ) = 3

Each call waits for its two children, then combines.

5 · Worked Examples

Example 1 Easy

Using count and leaves on the example tree, how many internal nodes are there? Check with n₀ = n₂ + 1.

Solution

Internal = 7 − 3 = 4 (1, 2, 3, 5). Nodes with two children: 1 and 2, so n₂ = 2 and n₀ = 3 = n₂ + 1. ✓

Example 2 Medium

What does this print?

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

Solution

f counts nodes with two children: 1 and 2 → 2. g returns the largest root-to-leaf sum: 1 + 2 + 5 + 7 = 15 (other paths: 1 + 2 + 4 = 7, 1 + 3 + 6 = 10).

Output

2 15

Example 3 GATE

What does this print?

int h(struct tnode *t, int d)
{
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return d;
    return h(t->left, d + 1) + h(t->right, d + 1);
}

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\n", h(root, 0));
    return 0;
}

Solution

h returns the sum of the depths of all leaves: leaf 4 at depth 2, 7 at depth 3, 6 at depth 2: 2 + 3 + 2 = 7.

Output

7

6 · GATE Traps

⚠️

• Height of an empty tree: −1 (edges) or 0 (nodes); the base case decides the convention.
• A leaf test needs both children NULL.
• Calling a recursive function twice in one expression (g in Example 2) doubles the work but not the result.
• Mirror must swap after (or before) recursing, not instead of recursing.
• In an expression tree, operands are always leaves.

8 · Memory Hook

🧠

“Ask both children, then add yourself.” Base case for NULL, combine for the node: count (1 +), height (1 + max), sum (data +).

9 · Connect the Dots

Lesson 4.4 answered questions about any binary tree in O(n). Finding one key in an arbitrary tree still means visiting every node. Next lesson answers: if keys are placed by a simple rule (smaller to the left, larger to the right), how fast can we find a key?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markHeight

A function returns 0 for NULL and 1 + max(left, right) otherwise. For a single node it returns:

• (A) 1
• (B) 2
• (C) −1
• (D) 0

Q2MCQ2 marksOutput

What does this print?

int count(struct tnode *t)  { return t == NULL ? 0 : 1 + count(t->left) + count(t->right); }
int leaves(struct tnode *t)
{
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return 1;
    return leaves(t->left) + leaves(t->right);
}
int height(struct tnode *t)                 /* edges; empty tree -1 */
{
    int a, b;
    if (t == NULL) return -1;
    a = height(t->left);
    b = height(t->right);
    return 1 + (a > b ? a : b);
}
int sum(struct tnode *t)    { return t == NULL ? 0 : t->data + sum(t->left) + sum(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 %d %d\n", count(root), leaves(root), height(root), sum(root));
    return 0;
}

• (A) 7 4 3 28
• (B) 6 3 3 28
• (C) 7 3 3 28
• (D) 7 3 4 28

Q3NAT2 marksExpression

Evaluate the expression tree with root −, left child * (children 6 and 3) and right child / (children 8 and 2).

Numerical answer: ________

Q4MCQ1 markMirror

After mirroring a binary tree, its inorder sequence is:

• (A) reversed
• (B) unchanged
• (C) the old preorder
• (D) the old postorder

Q5NAT2 marksOutput

What does this print?

int h(struct tnode *t, int d)
{
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return d;
    return h(t->left, d + 1) + h(t->right, d + 1);
}

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\n", h(root, 0));
    return 0;
}

Numerical answer: ________

11 · Rule Card

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

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

recursive tree functionscount / leaves / height / summirrorexpression tree

13 · Answer Vault