Trees & Binary Trees · Data Structures

A tree stores data in a hierarchy: one root at the top, and every other node has exactly one parent. File systems, the HTML of a web page, an organisation chart and a family tree are all trees.

A binary tree with root A. B and C are A's children; D, E, F and G are leaves.

Vocabulary

Term	Meaning (for the tree above)
Root	the top node with no parent — A
Parent / child	B is the parent of D and E
Siblings	nodes with the same parent — D and E
Leaf	a node with no children — D, E, F, G
Internal node	a node with at least one child — A, B, C
Edge	a link between parent and child (a tree with n nodes has n − 1 edges)
Depth of a node	edges from the root to it — depth(D) = 2
Height of a tree	edges on the longest root-to-leaf path — 2 here
Degree of a node	number of children — degree(A) = 2
Subtree	a node together with all its descendants

Binary trees

A binary tree is a tree where each node has at most two children, called left and right.

Type	Definition
Full (strict)	every node has 0 or 2 children
Perfect	full, and all leaves at the same level: 2ʰ⁺¹ − 1 nodes
Complete	every level full except possibly the last, which is filled left to right
Skewed	every node has only one child — basically a linked list
Balanced	heights of left and right subtrees differ by at most 1 at every node

Representing a binary tree

Linked representation — each node holds data plus left and right pointers:

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

Array representation — store level by level. For the node at index i (0-based): left child at 2i + 1, right child at 2i + 2, parent at (i − 1) / 2. Perfect for complete trees (like heaps); wasteful for skewed ones.

The tree above stored level by level. B is at index 1, so its children are at 3 (D) and 4 (E).

Traversals

A traversal visits every node once. Depth-first traversals differ only in when you visit the node relative to its subtrees:

Traversal	Order	Result for the tree above
Preorder	Node, Left, Right	A B D E C F G
Inorder	Left, Node, Right	D B E A F C G
Postorder	Left, Right, Node	D E B F G C A
Level order	level by level, left to right (uses a queue)	A B C D E F G

#include <stdio.h>
#include <stdlib.h>

typedef struct T { char data; struct T *left, *right; } T;

T *node(char d, T *l, T *r) { T *t = malloc(sizeof(T)); t->data = d; t->left = l; t->right = r; return t; }

void preorder(T *t)  { if (!t) return; printf("%c ", t->data); preorder(t->left); preorder(t->right); }
void inorder(T *t)   { if (!t) return; inorder(t->left); printf("%c ", t->data); inorder(t->right); }
void postorder(T *t) { if (!t) return; postorder(t->left); postorder(t->right); printf("%c ", t->data); }

void levelOrder(T *root) {
    T *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        T *t = queue[front++];
        printf("%c ", t->data);
        if (t->left)  queue[rear++] = t->left;
        if (t->right) queue[rear++] = t->right;
    }
}

int height(T *t) {
    if (!t) return -1;                         // empty tree has height -1
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}
int count(T *t)  { return t ? 1 + count(t->left) + count(t->right) : 0; }
int leaves(T *t) { return !t ? 0 : (!t->left && !t->right) ? 1 : leaves(t->left) + leaves(t->right); }

int main(void) {
    T *root = node('A', node('B', node('D', NULL, NULL), node('E', NULL, NULL)),
                        node('C', node('F', NULL, NULL), node('G', NULL, NULL)));
    printf("Preorder:    "); preorder(root);   printf("\n");
    printf("Inorder:     "); inorder(root);    printf("\n");
    printf("Postorder:   "); postorder(root);  printf("\n");
    printf("Level order: "); levelOrder(root); printf("\n");
    printf("Height %d, nodes %d, leaves %d\n", height(root), count(root), leaves(root));
    return 0;
}

Output

Preorder:    A B D E C F G 
Inorder:     D B E A F C G 
Postorder:   D E B F G C A 
Level order: A B C D E F G 
Height 2, nodes 7, leaves 4

Try it Yourself

Rebuilding a tree from traversals

Given inorder + preorder (or inorder + postorder), the tree is unique:

The first preorder element (or last postorder element) is the root.
Find the root in the inorder sequence: everything to its left is the left subtree, everything to its right is the right subtree.
Repeat for each subtree.

Preorder + postorder alone is not enough unless the tree is full.

Test yourself

4 questions · pick an answer to check it instantly

1
What is the inorder traversal of this tree: root 1, left child 2, right child 3, and 2 has a left child 4?
2
What is the maximum number of nodes in a binary tree of height 3?
3
In the array representation, where is the left child of the node at index 4 (0-based)?
4
Which traversal uses a queue?

#Vocabulary

#Binary trees

#Representing a binary tree

#Traversals

#Rebuilding a tree from traversals