Self-checkedTier 1 18 min readpds.trees-basics

Trees and binary trees

The vocabulary (root, leaf, depth, height, level, degree) and the counting facts GATE keeps using (n nodes have n - 1 edges, leaves = two-child nodes + 1, at most 2^h nodes on level h), the kinds of binary tree (full, complete, perfect, skewed), and how a tree is stored with pointers or in an array. The conventions that differ between books are marked.

Why it exists

Arrays and lists are lines: every item has one successor. Much real data is not a line. A folder holds folders, an arithmetic expression holds sub-expressions, a family has children and grandchildren, a decision splits into two cases that each split again. A tree is the structure for this branching, and a binary tree (at most two branches at every node) is the form that most exam questions use, because it is easy to store with two pointers and gives fast search when kept in order.

Prerequisites

Singly linked lists

Precise definitions

Words for any rooted tree

A tree is a set of nodes joined by edges so that there is exactly one path between any two nodes (it is connected and has no cycles). In a rooted tree one node is chosen as the root, and every other node hangs below it.

Term	Meaning
parent and child	the node directly above (towards the root) and the nodes directly below
siblings	children of the same parent
leaf (external node)	a node with no children
internal node	a node with at least one child
ancestor and descendant	any node on the path up to the root, and any node below
subtree of $v$	$v$ together with all its descendants
degree of a node	the number of its children
degree of a tree	the largest node degree
depth of a node	the number of edges on the path from the root to it. The root has depth 0.
level	the set of nodes at the same depth. This page numbers the root's level 0. Some books start at 1.
height of a node	the number of edges on the longest downward path from it to a leaf. A leaf has height 0.
height of the tree	the height of the root

Kinds of binary tree

A binary tree is a tree in which every node has at most two children, and the children are distinguished as left and right (a node with only a left child is a different tree from a node with only a right child).

Name	Definition on this page
Full (strict) binary tree	every node has 0 or 2 children
Perfect binary tree	full, and all leaves are on the same level. With height $h$ it has $2^{h+1} - 1$ nodes
Complete binary tree	every level is completely filled except possibly the last, and the last level is filled from the left
Skewed tree	every node has exactly one child except the last: all of them on the left (left-skewed) or all on the right (right-skewed), so there are exactly 2 such shapes for $n \ge 2$ , height $n - 1$ . A degenerate (chain-like) tree only needs at most one child per node, so zig-zag chains count: $2^{n-1}$ shapes, also height $n - 1$
Balanced tree	no single definition: AVL says the two subtree heights differ by at most 1 at every node. In general a family of trees is called balanced when its height stays $O(\log n)$

Counting facts

Let a tree have $n$ nodes, and let the binary tree have $n_0$ leaves, $n_1$ nodes with one child and $n_2$ nodes with two children. Heights are in edges and the root is at level 0.

Edges. Every tree with $n$ nodes has exactly $n - 1$ edges (every node except the root has one parent edge).
Nodes on a level. At most $2^i$ nodes on level $i$ .
Nodes in a tree of height $h$ . At least $h + 1$ (a chain) and at most $2^{h+1} - 1$ (perfect).
Height for $n$ nodes. $\lceil \log_2 (n+1) \rceil - 1 \le h \le n - 1$ . A complete binary tree with $n$ nodes has $h = \lfloor \log_2 n \rfloor$ .
Leaves. $n_0 = n_2 + 1$ . Reason: $n = n_0 + n_1 + n_2$ and the edge count $n - 1 = n_1 + 2n_2$ ; subtracting gives $n_0 = n_2 + 1$ .
Null pointers. In the pointer representation there are $2n$ child pointers and $n - 1$ of them are used, so $n + 1$ are NULL.
Full $k$ -ary trees. If every internal node has exactly $k$ children and there are $i$ internal nodes, then $n = k i + 1$ and the number of leaves is $(k - 1) i + 1$ .

Storing a binary tree

Pointer (linked) form. Each node is a block with the data and two pointers:

struct node {
    int data;
    struct node *left, *right;
};

An empty tree is NULL. For $n \ge 1$ , space is $n$ nodes plus $n + 1$ NULL pointers (the edge count $n - 1$ and the null count $n + 1$ are for $n \ge 1$ ).

Array form. Put the root in position 1 and the children of position $i$ in positions $2i$ and $2i + 1$ . The parent of position $i$ is $\lfloor i / 2 \rfloor$ . (With 0-based arrays: children $2i + 1$ and $2i + 2$ , parent $\lfloor (i - 1)/2 \rfloor$ .) This wastes space unless the tree is complete: a right-skewed tree of $n$ nodes needs $2^n - 1$ cells. The binary heap uses this form.
Left-child right-sibling. An ordinary tree whose nodes have any number of children can be stored as a binary tree: left points to the first child, right to the next sibling. Every rooted ordered tree corresponds to one binary tree.

How it works

Height is the standard recursive example, and it shows how all tree recursion works: handle the empty tree (here height $-1$ ), solve both subtrees, combine. Step through the run. The picture is drawn from the program's real left and right pointers. Watch how the numbers are combined as the calls return, and how an empty subtree is a call that returns at once.

Height of a tree, computed recursively

Real run

C source

1#include <stdio.h>

3struct node {

4 int data;

5 struct node *left, *right;

6};

8int height(const struct node *t) {

9 if (t == NULL)

10 return -1;

11 int l = height(t->left);

12 int r = height(t->right);

13 return 1 + (l > r ? l : r);

14}

Tree (read from the program's real pointers)

Recursive calls in progress (oldest on the left)

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

call on node 1

1 / 30

The tree (root 1; 2 has children 4 and 5; 5 has left child 7; 3 has right child 6) is built by setup code that is not shown. The function shown is the exact code that runs. Height here counts edges, so a single node has height 0 and an empty tree has height -1. Produced by: real execution: the tree, the call stack, the queue and the printed output are read from the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Worked examples

EX 1Size, leaves, height and two-child nodes

Easy

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int size(const struct node *t) {
    return t == NULL ? 0 : 1 + size(t->left) + size(t->right);
}
 
static int leaves(const struct node *t) {
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return 1;
    return leaves(t->left) + leaves(t->right);
}
 
static int height(const struct node *t) {
    if (t == NULL) return -1;
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}
 
static int two(const struct node *t) {
    if (t == NULL) return 0;
    return (t->left && t->right) + two(t->left) + two(t->right);
}
 
int main(void) {
    struct node *r = 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", size(r), leaves(r), height(r), two(r));
    return 0;
}

Output:

7 3 3 2

Reading it. The tree has 7 nodes. The leaves are 4, 7 and 6 (3 of them). The longest downward path is 1, 2, 5, 7: 3 edges, so the height is 3. Two nodes (1 and 2) have both children, and indeed $n_0 = n_2 + 1 = 3$ . Every one of these functions has the same shape: an empty tree gives a fixed answer, and the answer for a node combines the answers for its two subtrees.

EX 2Nodes on each level

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int at_level(const struct node *t, int level) {
    if (t == NULL) return 0;
    if (level == 0) return 1;
    return at_level(t->left, level - 1) + at_level(t->right, level - 1);
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    for (int lv = 0; lv <= 3; lv++) printf("%d ", at_level(r, lv));
    printf("\n");
    return 0;
}

Output:

1 2 3 1

Reading it. Level 0 holds the root. Level 1 holds 2 and 3. Level 2 holds 4, 5 and 6. Level 3 holds 7. The maximum possible on level $i$ is $2^i$ (1, 2, 4, 8). Level 2 holds 3 of a possible 4, so the tree is not complete. Counting the nodes of a level this way (going down $\text{level}$ steps) is the usual building block for level-based questions.

EX 3The same tree in an array

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static void store(const struct node *t, int i, int *a) {
    if (t == NULL) return;
    a[i] = t->data;
    store(t->left, 2 * i, a);
    store(t->right, 2 * i + 1, a);
}
 
int main(void) {
    struct node *r = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)),
                        mk(3, NULL, mk(6, NULL, NULL)));
    int a[16] = {0}; /* enough for this tree: the largest index is 10; a deeper chain would overflow */
    store(r, 1, a);
    for (int i = 1; i <= 10; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Output:

1 2 3 4 5 0 6 0 0 7

Reading it. Node 5 is at position 5, its left child 7 at $2 \cdot 5 = 10$ , and 6 (the right child of 3, which is at position 3) at $2 \cdot 3 + 1 = 7$ . Positions 6, 8 and 9 are empty (shown as 0). Seven nodes need 10 cells, because the tree is not complete. For a complete tree the $n$ nodes occupy exactly positions 1 to $n$ with no gaps.

EX 4Height of a complete binary tree

GATE level

#include <stdio.h>
 
int main(void) {
    int ns[8] = {1, 2, 3, 4, 7, 8, 15, 16};
    for (int k = 0; k < 8; k++) {
        int h = 0;
        for (int m = ns[k]; m > 1; m /= 2) h++;
        printf("%d ", h);
    }
    printf("\n");
    return 0;
}

Output:

0 1 1 2 2 3 3 4

Reading it. In a complete tree stored from position 1, the last node is at position $n$ , and the depth of position $i$ is the number of times $i$ can be halved before reaching 1, which is $\lfloor \log_2 i \rfloor$ . So 1 node has height 0, 2 and 3 nodes have height 1, 4 to 7 nodes have height 2, 8 to 15 have height 3, and 16 starts height 4. Note that 7 nodes (a perfect tree of height 2) and 8 nodes (one more, which opens a new level) differ in height. The same result for a general tree: the minimum height for $n$ nodes is $\lceil \log_2(n+1) \rceil - 1$ . This equals $\lfloor \log_2 n \rfloor$ for every $n \ge 1$ , so a complete tree always achieves the minimum height.

EX 5Using the counting formulas

GATE level

(a) Leaves and two-child nodes. A binary tree has 20 leaves. Then $n_2 = n_0 - 1 = 19$ . If it has no node with exactly one child (it is full), $n = n_0 + n_2 = 39$ . If instead it has 7 nodes with one child, $n = 20 + 19 + 7 = 46$ .

(b) A full 3-ary tree has 10 internal nodes. Then $n = 3 \cdot 10 + 1 = 31$ and the leaves are $31 - 10 = 21 = (3 - 1) \cdot 10 + 1$ .

(c) Edges. A tree with 50 nodes has 49 edges; a forest of 50 nodes and 5 trees has $50 - 5 = 45$ .

(d) Height range. A binary tree has 20 nodes. The minimum height is $\lceil \log_2 21 \rceil - 1 = 5 - 1 = 4$ and the maximum is $19$ .

(e) Null pointers. A binary tree with 20 nodes stored with pointers has $21$ null pointers.

Method. Write down the unknowns ( $n_0, n_1, n_2$ , $n$ ) and the two equations, nodes counted by type and edges counted two ways, and solve. Do not try to recall the formula in each new disguise.

EX 6Null pointers in a binary tree

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int nulls(const struct node *t) {
    return t == NULL ? 1 : nulls(t->left) + nulls(t->right);
}
 
int main(void) {
    struct node *r = 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", nulls(r));
    return 0;
}

Output:

Reading it. The 7 nodes have $2 \cdot 7 = 14$ child pointers. Six of them point at real nodes (the 6 edges), so $14 - 6 = 8 = n + 1$ are NULL. This is the count of calls on an empty tree made by the usual recursive traversal (the form that tests for NULL at the top and recurses into both children unconditionally), which is why such a traversal makes $2n + 1$ calls in total. A version that tests if (t->left) before calling would make only $n$ calls.

Cheat box

Tree with $n$ nodes: $n - 1$ edges. Root depth 0. Leaf height 0 (edges). Empty tree height $-1$ . Check the convention.
Binary tree: $n_0 = n_2 + 1$ . $n = n_0 + n_1 + n_2$ . Null pointers $= n + 1$ .
Level $i$ : at most $2^i$ nodes. Height $h$ : at most $2^{h+1} - 1$ , at least $h + 1$ nodes.
Height of $n$ nodes: between $\lceil \log_2(n+1) \rceil - 1$ and $n - 1$ . Complete: $\lfloor \log_2 n \rfloor$ .
Full $k$ -ary with $i$ internal nodes: $n = k i + 1$ , leaves $= (k-1) i + 1$ .
Full: 0 or 2 children. Perfect: full with all leaves on one level. Complete: filled level by level, left to right.
Array form (1-based): children $2i, 2i+1$ ; parent $\lfloor i/2 \rfloor$ . 0-based: $2i+1, 2i+2$ ; $\lfloor (i-1)/2 \rfloor$ .
Tree recursion: answer for the empty tree, combine the answers for the two subtrees.

Traps and GATE patterns

Connections

Builds on

Singly linked lists

Unlocks

CIDR and subnettinganalogous to Binary tree traversalsPrerequisite of Counting binary treesPrerequisite of Binary heaps and heap operationsPrerequisite of

Across subjects

B treesanalogous-to

Within this subject

Binary tree traversalsuses Counting binary treesuses Binary search treesuses Binary heaps and heap operationsuses Arrays and indexinguses

The node with two pointers is the linked list node with one more link. Visiting every node in a fixed order is the subject of tree traversals; keeping keys in order gives the binary search tree; and the array form with complete shape is the binary heap. How many distinct trees exist for $n$ nodes is the question of tree counting. Database indexes use the same idea with more branches per node (B-trees).

PYQs

3 previous year questions from your book. I re-solved each one myself (1 by running or simulating, 2 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2014 · Set 1Q27 · page 69 of the book

Consider it to rooted n node binary tree represented
using pointers. The best upper bound on the time
required to determine the number of subtrees having
having exactly 4 nodes O(na logb n). Then the value of
a + 10b is

DATA STRUCTURE

(a)1
(b)11
(c)12
(d)21

GATE 2014 · Set 3Q30 · page 70 of the book

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 tree)
{
int value=0;
if (tree != NULL) {
if (tree->leftMostChild == NULL) value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}
DATA STRUCTURE

When the pointer to the root of a tree is passed as
the argument to DoSomething, the value returned
by the function corresponds to the

(a)number of internal nodes in the tree.
(b)height of the tree.
(c)number of nodes without a right sibling in the tree.
(d)number of leaf nodes in the tree.

GATE 2012 · MCQQ33 · page 71 of the book

The height of a tree is defined as the number of edges
on the longest path in the tree. The function shown in
the pseudocode 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; // Box 1
else
{
h1 = height(n -> left);
if(n -> right == NULL) return (1+h1);
else{h2 = height(n -> right);
return B2; // Box 2}
}

The order in which the nodes are visited during in-
order traversal is

(a)SQPTRWUV
(b)SQPTURWV
(c)SQPTWUVR
(d)SQPTRUWV

Self-check

Question 1

A binary tree has 15 nodes and every node has 0 or 2 children. How many leaves does it have, and how many internal nodes?

Show answer

$n_1 = 0$ , so $n = n_0 + n_2$ and $n_0 = n_2 + 1$ . Then $15 = 2 n_2 + 1$ , so $n_2 = 7$ internal nodes and $n_0 = 8$ leaves.

Question 2

What is the maximum number of nodes in a binary tree of height 4 (edges, root at level 0)? And the minimum height of a binary tree with 100 nodes?

Show answer

Maximum $2^{4+1} - 1 = 31$ . For 100 nodes: $2^{h+1} - 1 \ge 100$ needs $h + 1 \ge 7$ (since $2^6 - 1 = 63 < 100 \le 127$ ), so the minimum height is 6, which equals $\lceil \log_2 101 \rceil - 1 = 7 - 1$ .

Question 3

A complete binary tree is stored in an array from position 1. Which positions are the children and the parent of position 13? How many nodes can be below position 13 if the tree has 20 nodes?

Show answer

Children would be $26$ and $27$ and the parent is $\lfloor 13/2 \rfloor = 6$ . With 20 nodes the positions only go up to 20, so position 13 has no children (it is a leaf).

Question 4

In a binary tree with 40 nodes, 17 leaves and no other constraint, how many nodes have exactly one child?

Show answer

$n_2 = n_0 - 1 = 16$ . Then $n_1 = 40 - 17 - 16 = 7$ .

Question 5

What is the height of this tree in edges and in nodes: a root with one child, which has one child?

Show answer

It is a chain of 3 nodes: height 2 counted in edges, 3 counted in nodes. This is why the convention must be stated.

Revision card

One-screen revision

Tree: $n$ nodes, $n - 1$ edges. Binary: at most 2 children, left and right distinguished.
Depth and height in edges; root depth 0; leaf height 0; empty tree $-1$ . Check the convention.
$n_0 = n_2 + 1$ . Null pointers $= n + 1$ . Level $i$ : $\le 2^i$ . Height $h$ : $\le 2^{h+1} - 1$ nodes.
Min height $\lceil \log_2(n+1) \rceil - 1$ ; complete: $\lfloor \log_2 n \rfloor$ ; max $n - 1$ .
Full $k$ -ary: $n = k i + 1$ .
Array: children $2i$ , $2i + 1$ ; parent $\lfloor i/2 \rfloor$ (1-based).
Full (0 or 2 children), perfect, complete (left-filled), skewed.
Tree recursion: base case plus combine two subtrees.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 10.4 Representing rooted trees, Appendix B.5 Trees (free, rooted and ordered trees, degree, depth, height, full and complete)
·Kernighan and Ritchie, The C Programming Language, 2nd ed., Section 6.5 Self-referential Structures (a binary tree of words)

Verification

The animation replays a real run of a C program on a real tree: the tree is drawn from the program's left and right pointers, and the computed heights are the program's own. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan (with leak detection off; the examples build small trees and do not free them). The counting facts were checked by enumerating every binary tree shape up to 8 nodes in a one-off script that is not part of the repository. Conventions that differ between books (the level of the root, whether height counts edges or nodes, and the meaning of 'full' and 'complete') are marked and need confirming against real GATE questions. The textbook section numbers were written from memory and have NOT been checked against the books. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Recursion patterns

Binary tree traversals