Trees

A tree represents hierarchy. Every non-root node has one parent, and every node may own a collection of children. This single-parent rule gives each node one unique structural route from the root, unlike a general graph where several routes and cycles may exist.

Trees model syntax, documents, directories, decisions, organizational relationships, spatial subdivisions, and nested state. The structure is recursive: a tree is either empty or consists of a root whose children are themselves roots of subtrees.

Why Do We Need Trees?

Arrays and linked lists arrange values in one line. That is useful for a sequence, but many situations contain levels and groups inside groups.

Consider the outline of a book:

Data Structures
├── Linear Structures
│   ├── Arrays
│   ├── Linked Lists
│   ├── Stacks
│   └── Queues
└── Non-linear Structures
    ├── Trees
    └── Graphs

A flat list can store the seven topic names, but the list alone does not say that Stacks belongs to Linear Structures or that Trees belongs to Non-linear Structures. Extra parent-child information is required.

A tree makes those relationships part of the structure. It lets a program ask:

• Which item is at the top?
• Which items are directly inside this group?
• What are all descendants of this item?
• What path leads from the root to a particular item?
• How deep is an item?
• Can one complete branch be visited, copied, moved, or deleted?

The important feature is not that a tree stores more values. Other structures already store values. A tree stores hierarchical relationships.

Everyday Hierarchies

• Book outline: a book contains chapters, chapters contain sections, and sections may contain subsections.
• Organization chart: a director supervises managers, and each manager supervises a team.
• Folder system: a folder contains files and more folders; moving one folder moves everything below it.
• Classification system: a broad category divides into narrower categories.
• Tournament bracket: two competitors or teams feed into the next match.
• Yes/no decision guide: each answer selects one of two possible next questions.

Not every object commonly called a “tree” is a strict data-structure tree. A real family genealogy may give a person multiple parents and merge branches, so its complete relationship model is closer to a graph. The single-parent rule matters in this chapter.

Trees in Software

• File systems: directories contain files and subdirectories. A complete directory branch can be traversed recursively.
• HTML DOM: an HTML document contains nested elements such as body, section, p, and a. Browsers traverse this structure to render and update pages.
• Compiler syntax trees: operators and language constructs become internal nodes; identifiers and literal values often appear near the leaves.
• User-interface trees: windows, panels, forms, buttons, and labels are nested so layout and events can move through parent-child relationships.
• Menu and category systems: applications and online stores arrange choices from broad groups to narrower items.
• Expression trees: operators are parents of their operands, allowing prefix, infix, and postfix processing.
• Decision and game trees: each branch represents a possible choice or outcome.
• Database query plans: joins, scans, filters, and sorts form an execution tree whose children provide input to their parent operation.
• Heaps and search trees: special binary trees support priority queues and ordered lookup.

Many real implementations store these logical trees using pointers, arrays, parent indexes, or database rows. “Tree” describes the relationships and rules; it does not require nodes to appear physically in a tree shape in memory.

Graph vs Tree

A tree is a restricted kind of graph. Both structures contain nodes and connections, but a tree removes the ambiguity that general graph connections may create.

Tree:                         Graph:

      A                            A
     / \                          / \
    B   C                        B---C
   /                              \ /
  D                                D

In the tree, D has one parent and one route from A: A -> B -> D.

In the graph, D can be reached through B or C. The connections A-B-C-A also form a cycle. Those features are valid in a graph but violate tree rules.

For an undirected connected graph, being acyclic and having exactly one simple path between every pair of nodes are equivalent ways to recognize a tree. A rooted tree then chooses one node as the root and interprets connections as parent-child relationships.

The edge-count rule needs context. A connected acyclic graph with n nodes has n - 1 edges. Merely counting n - 1 edges is not enough: a graph could contain a cycle in one component and leave another node disconnected.

A DAG Is Not Necessarily a Tree

A directed acyclic graph (DAG) has no directed cycle, but a node may still have several parents:

    A
   / \
  B   C
   \ /
    D

Here D has two parents, and there are two routes from A to D. The structure is a DAG, not a tree.

When a Software Tree Becomes a Graph

• A directory hierarchy is tree-like when every item has one containing directory. Shortcuts, symbolic links, or shared references can add graph connections and even cycles.
• A DOM node normally has one parent, so the document structure is a tree. A separate reference from one element to another does not become an owned child link.
• A strict organization chart is a tree. Multiple managers and cross-team reporting relationships make the complete organization a graph.
• A course outline is a tree because each subsection belongs to one section. A prerequisite network is a graph because one course may require several earlier courses.

Use a tree when each item needs one structural parent and one unambiguous route from the root. Use a graph when shared dependencies, cross-links, multiple routes, or cycles are part of the problem rather than errors.

Why Binary Trees?

A general tree may give a node any number of children. A binary tree limits each node to two named positions: left and right.

That restriction is useful when the problem naturally has two parts:

• an arithmetic operator usually has a left and right operand;
• a yes/no decision has two outcomes;
• a comparison can divide values into smaller and larger groups;
• a tournament match combines two participants;
• a divide-and-conquer step may split one problem into two subproblems.

Two child pointers also make the recursive pattern consistent:

process current node
process left subtree
process right subtree

A binary tree is not automatically a binary search tree. Binary describes the number and identity of child positions. Search-tree ordering is an additional rule introduced in the next chapter.

When Is a Tree the Wrong Choice?

• Use an array or linked list when the data is mainly one sequence.
• Use a hash table when exact lookup is the main operation and sorted order is unnecessary.
• Use a graph when an object may have several parents, arbitrary cross-links, or cycles.
• Use a database table with indexes when the data is persistent, shared, and larger than an in-memory structure should manage alone.

Choosing a tree makes sense when hierarchy, recursive subgroups, or ordered branching is central to the problem.

Tree Model

A rooted tree can be defined as a set of nodes with directed parent-to-child relationships such that:

1. one distinguished node is the root;
2. the root has no parent;
3. every other node has exactly one parent;
4. every node is reachable from the root;
5. following child relationships never returns to an earlier node.

Example:

             A
          /  |  \
         B   C   D
        / \       \
       E   F       G

The node set is {A,B,C,D,E,F,G}. The parent-child edges are:

A->B, A->C, A->D, B->E, B->F, D->G

Ignoring direction, a non-empty tree with n nodes always has n - 1 edges. Every node except the root contributes exactly one incoming parent edge.

Tree Vocabulary

Root

A is the root. It is the entry point from which the whole structure is reachable.

Parent

B is the parent of E and F. A node has at most one parent in a tree.

Child

E and F are children of B. Child order may be meaningful, as in an ordered syntax tree, or irrelevant, as in some taxonomies.

Sibling

Nodes sharing a parent are siblings. B, C, and D are siblings.

Ancestor

An ancestor lies on the parent chain above a node. The proper ancestors of F are B and A. Some definitions include a node as its own non-proper ancestor; state the convention when it matters.

Descendant

A descendant lies below a node. E and F are descendants of B; they are also descendants of A.

Leaf

A leaf has no children. The example’s leaves are C, E, F, and G.

Internal node

An internal node has at least one child. A, B, and D are internal.

Subtree

A subtree rooted at B contains B and all of its descendants:

       B
      / \
     E   F

Subtrees are structural views, not arbitrary connected subsets. Removing a subtree cuts exactly the parent edge above its root.

Tree Properties

Depth

The depth of a node is the number of edges from the root to it:

depth(A) = 0
depth(B) = 1
depth(F) = 2

Level

Many texts use level as a synonym for depth. Others number the root at level 1. This chapter uses zero-based levels, so level(v) == depth(v).

Height definition

The height of a node is the maximum number of edges on a downward path from that node to a leaf:

height(leaf) = 0
height(node) = 1 + max(height(child))

The height of the tree is the height of its root. For an empty tree, common conventions are -1 edges or 0 nodes. The implementation below returns -1 so a leaf naturally has height 0.

Depth describes a node from above; height describes it from below.

Degree

The degree of a node is its number of children. The degree of a tree is the maximum node degree. The example has tree degree 3 because A has three children.

Width

The width at level d is the number of nodes at that depth. The maximum width is useful when estimating the space required by level-order processing.

Tree Types

General trees

A general rooted tree permits any number of children per node. The example rooted at A is general because A has three children.

Binary trees

A binary tree gives each node at most two distinguished positions: left child and right child.

          8
        /   \
       3     10
        \    /
         6  9

The distinction between left and right matters. Swapping them produces a different ordered binary tree even when values and parent relationships remain the same.

A binary tree has no automatic key-order rule. Search ordering belongs to Search Trees; completeness belongs to Heaps. Shape alone defines a binary tree.

Full trees

A full binary tree has either zero or two children at every node:

        A
       / \
      B   C
         / \
        D   E

If a full binary tree has i internal nodes, it has i + 1 leaves and 2i + 1 total nodes.

Perfect trees

A perfect binary tree is full and all leaves occur at the same depth:

           A
         /   \
        B     C
       / \   / \
      D   E F   G

At height h, a perfect binary tree has:

nodes  = 2^(h + 1) - 1
leaves = 2^h

Complete binary trees

A complete binary tree fills every level except possibly the last, and fills the last from left to right:

           A
         /   \
        B     C
       / \   /
      D   E F

Completeness makes an array representation gap-free. Binary heaps require this shape.

Balanced trees

Informally, a balanced tree keeps height proportional to log n. A particular data structure must define a precise balance rule. AVL trees constrain child-subtree heights; red-black trees constrain colors and black-height. Merely looking visually symmetric is not a definition.

Skewed trees

A skewed binary tree has a long one-child chain:

A
 \
  B
   \
    C
     \
      D

Its height is n - 1, so operations that follow the height become linear. Shape, not just node count, controls many tree costs.

Tree Representation

The best representation follows child-count rules and dominant operations.

Linked nodes

A binary node stores two child links:

typedef struct TreeNode {
    char value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

Null links encode absent child positions. This supports arbitrary binary shapes and local subtree attachment. Each node needs two pointers even when it is a leaf.

A general-tree node may store a dynamic child array:

typedef struct GNode {
    int value;
    struct GNode **children;
    size_t child_count;
    size_t child_capacity;
} GNode;

This makes indexed child access constant time and keeps child pointers contiguous, but adding children may relocate the child-pointer array.

Parent-index storage

When vertices use dense IDs, store each node’s parent:

node:    A  B  C  D  E  F  G
index:   0  1  2  3  4  5  6
parent: -1  0  0  0  1  1  3

Parent lookup is constant time. Enumerating children requires scanning all nodes unless child indexes are added. The root uses a distinguished value such as SIZE_MAX rather than -1 when IDs are unsigned.

Parent arrays are compact for static hierarchies and useful in disjoint-set forests, but they do not alone make downward traversal efficient.

Child lists

Store one collection of child IDs per node:

A: B, C, D
B: E, F
C: empty
D: G
E: empty
F: empty
G: empty

This is the tree-specialized form of an adjacency list. It supports downward traversal in time proportional to the number of children visited. Add a parent field if upward navigation must also be efficient.

Sibling links

The left-child right-sibling representation stores two links per general-tree node:

• first_child: the node’s first child;
• next_sibling: the next child of the same parent.

general tree                  link interpretation

      A                       A
   /  |  \                    |
  B   C   D                   B -> C -> D
 / \       \                  |         |
E   F       G                 E -> F    G

Every general tree becomes a binary-shaped link structure without imposing a two-child limit. Finding the kth child requires walking sibling links.

Sequential storage

Complete binary trees fit arrays with zero-based formulas:

left(i)   = 2i + 1
right(i)  = 2i + 2
parent(i) = floor((i - 1) / 2), for i > 0

tree:                    array:
        A                [A, B, C, D, E, F]
      /   \
     B     C
    / \   /
   D   E F

An arbitrary skewed tree wastes most array positions because missing ancestors create gaps. Sequential storage is a shape-dependent choice, not a universal tree layout.

Tree Invariants

For an owned linked binary tree:

• each reachable non-root node is referenced as a child exactly once;
• no child link points to an ancestor;
• left and right either point to valid owned subtree roots or are null;
• all owned nodes are reachable from the root;
• no node is shared by two child positions unless the structure is intentionally a DAG—a directed acyclic graph, which may let multiple parents reach the same node—rather than a tree.

The last distinction is important. This shape:

    A
   / \
  B   C
   \ /
    D

is not a tree when both B and C own D, because D has two parents. Recursive destruction would attempt to free D twice.

Binary Tree: Function-by-Function

The first implementation uses one TreeNode *root and one function for each responsibility. It deliberately avoids a tree wrapper, double pointers, and a dynamically growing traversal queue. Those techniques are useful later, but they are not needed to understand the basic algorithms.

Tree State: The Root Pointer

The simplest tree state is one pointer:

TreeNode *root = NULL;

root == NULL means the tree is empty. Otherwise, root points to the top node, and every other node is reached by following left and right links.

The name root plays the same structural role that head plays in a linked list: it is the entry point. During recursion, a parameter named root means “the root of the subtree handled by this call,” so it may temporarily point to B, D, or any other node without changing the program’s original root pointer.

Node Creation

Each binary-tree node stores one value and two child pointers:

typedef struct TreeNode {
    char value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

left and right must begin as NULL because a new node has no children yet.

TreeNode *createTreeNode(char value) {
    TreeNode *newNode = malloc(sizeof(TreeNode));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

This introductory version stops the program if allocation fails. That keeps the tree operations focused on links and recursion. A reusable library would normally report the failure to its caller instead.

Insert a Left or Right Child

Unlike a BST, an ordinary binary tree has no ordering rule that chooses an insertion position. The caller must say whether the new node belongs on the left or right of a particular parent.

TreeNode *insertLeftChild(TreeNode *parent, char value) {
    if (parent == NULL || parent->left != NULL) {
        return NULL;
    }

    parent->left = createTreeNode(value);
    return parent->left;
}

TreeNode *insertRightChild(TreeNode *parent, char value) {
    if (parent == NULL || parent->right != NULL) {
        return NULL;
    }

    parent->right = createTreeNode(value);
    return parent->right;
}

Each function returns the inserted child so it can later become a parent itself. It returns NULL when the requested child position is already occupied or the parent does not exist. Silently replacing an existing child could lose an entire subtree.

A different API could define “insert at the first open position in level order,” but that would impose a complete-tree shape. Explicit left/right insertion lets us build any binary-tree shape, including an uneven one.

The parent pointer is the insertion position. For example:

TreeNode *nodeB = insertLeftChild(root, 'B');
TreeNode *nodeD = insertLeftChild(nodeB, 'D');

The first call changes root->left and returns the new node B. The second call uses that returned pointer as the parent and changes B->left.

If the same position is used again, insertion fails without changing the tree:

TreeNode *result = insertLeftChild(root, 'X');

if (result == NULL) {
    printf("Left child is already occupied\n");
}

Here root->left already points to B, so X is not created and the subtree beginning at B remains connected.

Building an Uneven Tree

The examples extend the earlier A–F tree instead of replacing it. Nodes G through J add one deeper level to the left subtree, while the right subtree remains shorter:

                 A
               /   \
              B     C
             / \     \
            D   E     F
           / \ / \
          G  H I  J

Its height is 3 when height counts edges. The left subtree has paths such as A -> B -> D -> G, while the right subtree’s longest path, A -> C -> F, has only two edges.

The tree can be built one parent-child relationship at a time:

TreeNode *root = createTreeNode('A');
TreeNode *nodeB = insertLeftChild(root, 'B');
TreeNode *nodeC = insertRightChild(root, 'C');
TreeNode *nodeD = insertLeftChild(nodeB, 'D');
TreeNode *nodeE = insertRightChild(nodeB, 'E');

insertRightChild(nodeC, 'F');
insertLeftChild(nodeD, 'G');
insertRightChild(nodeD, 'H');
insertLeftChild(nodeE, 'I');
insertRightChild(nodeE, 'J');

The variable names record which existing node is acting as the parent. For example, insertLeftChild(nodeD, 'G') directly says that G becomes the left child of D.

After construction, root is the only pointer required to reach the entire tree. The temporary names such as nodeB and nodeD make construction readable; traversal functions still begin with only root.

Tree Traversal

The easiest way to remember the four traversals is to focus on when the root of the current subtree is visited.

The three depth-first traversals contain the same three actions:

process the root
traverse the left subtree
traverse the right subtree

Only the order of those actions changes. Level order uses a different idea: it visits the tree row by row.

A recursive call explores an entire subtree before returning; “left” does not mean only the immediate left child. During recursion, each node becomes the root of its own smaller subtree.

Use the uneven tree to compare all four orders. In the experiment, . marks an absent child.

How Recursion Moves Through a Tree

Each call receives the root of one subtree. Consider the subtree rooted at D:

      D
     / \
    G   H

Calling inorderTraversal(nodeD) produces this sequence of calls and returns:

inorderTraversal(D)
  inorderTraversal(G)
    left is NULL  -> return
    print G
    right is NULL -> return
  print D
  inorderTraversal(H)
    left is NULL  -> return
    print H
    right is NULL -> return

Output: G D H

The program does not need a special function for a subtree. Passing nodeD instead of root simply makes D the root of the current recursive problem.

Preorder

Preorder processes the root before either subtree:

root -> left -> right

PRE: the root of the current subtree comes first.

void preorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    printf("%c ", root->value);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

For the uneven tree, preorder prints:

A B D G H E I J C F

The first value is A because the root is processed immediately. The complete left subtree—B D G H E I J—finishes before traversal enters the shorter right subtree—C F.

Preorder is useful when a parent must be handled before its descendants, such as copying a tree or writing a prefix expression.

Inorder

Inorder processes the root between its two subtrees:

left -> root -> right

IN: the root of the current subtree comes in the middle.

void inorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    inorderTraversal(root->left);
    printf("%c ", root->value);
    inorderTraversal(root->right);
}

For the uneven tree, inorder prints:

G D H B I E J A C F

Node C has no left child, so its left call returns immediately and C is printed before traversal enters F. Deeper node D has two children, so inorder prints G, then D, then H. Missing children and uneven depth change when calls return, but they do not change the inorder rule.

Inorder is defined for binary trees because left and right positions are distinct. It produces sorted output only when the tree is a binary search tree.

Postorder

Postorder processes the root after both subtrees:

left -> right -> root

POST: the root of the current subtree comes last.

void postorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%c ", root->value);
}

For the uneven tree, postorder prints:

G H D I J E B F C A

The root A appears last because neither subtree is unfinished when it is processed. This makes postorder useful for freeing a tree: children can be freed before their parent.

The Best Memory Trick

For the first three traversals, remember only where the current root appears:

PRE   = root before its subtrees
IN    = root between its subtrees
POST  = root after its subtrees
LEVEL = row by row

For example, the subtree rooted at D contains D, G, and H. Its preorder is D G H, its inorder is G D H, and its postorder is G H D.

The base case is equally important in all three functions:

if (root == NULL) {
    return;
}

It stops recursion at every missing child. Without this check, a traversal would try to read fields through a null pointer.

Level Order

Level-order traversal visits nodes from top to bottom and left to right:

A B C D E F G H I J

LEVEL ORDER: visit the tree row by row.

Recursion naturally follows one branch deeply, so level order uses a queue instead. This teaching version uses a fixed array large enough for the example:

#define MAX_TREE_NODES 100

void levelOrderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    TreeNode *queue[MAX_TREE_NODES];
    int front = 0;
    int rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        TreeNode *currentNode = queue[front++];
        printf("%c ", currentNode->value);

        if (currentNode->left != NULL) {
            queue[rear++] = currentNode->left;
        }
        if (currentNode->right != NULL) {
            queue[rear++] = currentNode->right;
        }
    }
}

front identifies the next node to visit. rear identifies the next free queue position. Visiting C adds only F because C has no left child. Visiting D later adds G and H, while E adds I and J. The queue therefore handles the one missing child without losing deeper nodes.

The first six queue steps are:

Every node enters the queue once and leaves it once. Children are added only after their parent is removed, which keeps shallower levels ahead of deeper levels.

The fixed queue assumes the tree contains at most MAX_TREE_NODES nodes. A reusable version should use the dynamically growing or circular queue techniques from the Queues chapter.

Traversal Costs

Every complete traversal visits each of n nodes once, so time is Theta(n). Extra space depends on shape:

• recursive depth-first traversal uses O(h) call frames;
• level order uses a queue whose maximum size is the tree’s maximum width, up to O(n).

An uneven or skewed tree can make recursive depth much larger on one side. In the worst case, a chain of n nodes uses O(n) recursive frames.

Tree Measurements: Function-by-Function

Measurements use the same recursive idea as traversal, but each call returns a number.

Count Nodes

An empty subtree contains zero nodes. A non-empty subtree contains its root plus all nodes in its two subtrees.

int countNodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }

    return 1 + countNodes(root->left)
             + countNodes(root->right);
}

For the example, the left subtree contains seven nodes (B, D, E, G, H, I, J) and the right subtree contains two (C, F), so the total is 1 + 7 + 2 = 10.

Count Leaves

A leaf has neither a left nor a right child:

int countLeafNodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

The example has five leaves: F, G, H, I, and J. Node C is not a leaf merely because its left pointer is NULL; it still has a right child.

Find Height

This chapter counts height in edges, so an empty tree has height -1 and a leaf has height 0.

int calculateHeight(TreeNode *root) {
    if (root == NULL) {
        return -1;
    }

    int leftHeight = calculateHeight(root->left);
    int rightHeight = calculateHeight(root->right);

    if (leftHeight > rightHeight) {
        return 1 + leftHeight;
    }
    return 1 + rightHeight;
}

At root A, the left-subtree height is 2 and the right-subtree height is 1. The function chooses the larger result and returns 1 + 2 = 3. This is why height follows the deepest side rather than averaging the two sides.

Height is calculated while recursion returns from the leaves:

This bottom-up calculation is postorder in spirit: both child results must be known before the parent can calculate its own height.

Each measurement visits every node, so each takes Theta(n) time.

Free the Tree

Memory cleanup is a postorder operation. The function frees both child subtrees before freeing their parent:

void freeTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

Freeing the parent first would lose the safe way to read its left and right pointers.

Common Beginner Mistakes

Treating a Binary Tree Like a BST

An ordinary binary tree does not compare values during insertion. insertLeftChild(nodeB, 'D') describes a position; the character D does not decide that position.

Forgetting the Null Base Case

Every leaf has two null child links. Recursive functions must stop at those links before reading root->value, root->left, or root->right.

Traversing Only Immediate Children

Printing root, root->left, and root->right visits at most three nodes. A traversal must recursively process the complete left and right subtrees.

Mixing Height Conventions

This program counts edges: an empty tree has height -1, a leaf has height 0, and the example has height 3. A node-count convention would report one more. Either convention works, but formulas and expected answers must use one consistently.

Losing an Existing Subtree

Assigning a new pointer directly to an occupied child field disconnects the old subtree. The insertion helpers reject occupied positions so replacement cannot happen accidentally.

Binary Tree: Full Code

This compact program keeps only node creation and the four traversals. The main function creates the same uneven tree used in every trace and connects its nodes directly.

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

#define MAX_NODES 100

struct Node {
    char data;
    struct Node *left;
    struct Node *right;
};

struct Node* createNode(char data) {
    struct Node* newNode = malloc(sizeof(struct Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

void preorder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    printf("%c ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void inorder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    inorder(root->left);
    printf("%c ", root->data);
    inorder(root->right);
}

void postorder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    postorder(root->left);
    postorder(root->right);
    printf("%c ", root->data);
}

void levelOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    struct Node* queue[MAX_NODES];
    int front = 0;
    int rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        struct Node* current = queue[front++];
        printf("%c ", current->data);

        if (current->left != NULL) {
            queue[rear++] = current->left;
        }
        if (current->right != NULL) {
            queue[rear++] = current->right;
        }
    }
}

int main(void) {
    struct Node* root = createNode('A');

    root->left = createNode('B');
    root->right = createNode('C');

    root->left->left = createNode('D');
    root->left->right = createNode('E');
    root->right->right = createNode('F');

    struct Node* nodeD = root->left->left;
    struct Node* nodeE = root->left->right;

    nodeD->left = createNode('G');
    nodeD->right = createNode('H');
    nodeE->left = createNode('I');
    nodeE->right = createNode('J');

    printf("Preorder: ");
    preorder(root);

    printf("\nInorder: ");
    inorder(root);

    printf("\nPostorder: ");
    postorder(root);

    printf("\nLevel order: ");
    levelOrder(root);

    return 0;
}

Expected output:

Preorder: A B D G H E I J C F
Inorder: G D H B I E J A C F
Postorder: G H D I J E B F C A
Level order: A B C D E F G H I J

Expression Trees

An expression tree stores operators in internal nodes and operands in leaves:

expression: (7 + 3) * (9 - 4)

             *
           /   \
          +     -
         / \   / \
        7   3 9   4

Traversal connects structure to notation:

preorder:  * + 7 3 - 9 4       prefix
inorder:   7 + 3 * 9 - 4       needs parentheses to preserve shape
postorder: 7 3 + 9 4 - *       postfix

Evaluation is postorder in spirit: evaluate both child subtrees, then apply the root operator.

bool evaluate(const ExprNode *root, double *out) {
    if (root == NULL || out == NULL) {
        return false;
    }
    if (root->kind == NUMBER) {
        *out = root->number;
        return true;
    }

    double left, right;
    if (!evaluate(root->left, &left) ||
        !evaluate(root->right, &right)) {
        return false;
    }

    switch (root->op) {
        case '+':
            *out = left + right;
            return true;
        case '-':
            *out = left - right;
            return true;
        case '*':
            *out = left * right;
            return true;
        case '/':
            if (right == 0.0) {
                return false;
            }
            *out = left / right;
            return true;
        default:
            return false;
    }
}

The node needs a tag such as kind because interpreting an operator byte as a number—or vice versa—would violate the representation.

Decision Trees

A decision tree stores a test at each internal node and an outcome at each leaf:

             age >= 18?
             /        \
           no          yes
        "minor"     has ID?
                    /     \
                  no       yes
              "reject"  "accept"

Evaluation follows one root-to-leaf path. Its cost is proportional to that leaf’s depth, not necessarily the total number of nodes.

Decision trees expose why balance matters: a shallow tree reduces worst-case questions, while an unbalanced tree may make common decisions fast at the cost of rare deep paths. How a machine-learning system constructs a decision tree is an algorithmic/statistical topic; the data structure stores and evaluates the resulting hierarchy.

Tree Storage

Linked binary nodes

Storage is Theta(n) with two child pointers per node, including null pointers. Nodes can be attached locally but separate allocations add overhead and weaken locality.

General child vectors

Storage is Theta(n + e), where a tree has e = n - 1 child references. Each node may also hold unused vector capacity.

Parent-index costs

One parent ID per node gives compact Theta(n) storage and strong locality. Downward queries need a scan or a supplemental child index.

Sequential binary storage

Complete trees use exactly n occupied slots. Arbitrary trees may require an index as large as 2^h, wasting exponential space relative to node count in the most skewed shapes.

Choosing Trees

Choose linked binary nodes when shape is arbitrary and subtree updates dominate. Choose sequential storage when the tree is complete or nearly complete. Choose parent arrays for static hierarchies dominated by upward navigation. Choose child vectors for ordered general trees and left-child right-sibling links when a uniform two-link node is valuable.

Consider parent links only when upward operations justify another invariant. With both parent and child links, attachment and detachment must update both directions consistently.

Subtree Ownership

A child pointer does more than describe shape when the tree owns its nodes. It also answers, “Who must eventually free this subtree?” A useful ownership contract is:

root variable owns the root subtree
node->left owns the complete left subtree
node->right owns the complete right subtree
NULL owns nothing

Under this contract, attachment transfers ownership to the parent. The caller must stop treating the child as independently owned after a successful attachment. Detachment performs the reverse transfer: it clears the parent’s link and returns the subtree root to the caller.

static TreeNode *detach_left(TreeNode *parent) {
    if (parent == NULL) {
        return NULL;
    }
    TreeNode *detached = parent->left;
    parent->left = NULL;
    return detached;
}

Suppose B is the left child of A, and X has an empty right position. A safe move is:

1. detach B from A       A no longer owns B; caller owns B
2. attach B under X      X now owns B; caller no longer owns B

The failure between those steps matters. If attaching to X fails, the caller still owns B and must either attach it back, attach it somewhere else, or destroy it. A convenience operation such as move_left(source, destination) can validate the destination before detaching so a rejected move changes nothing.

Replacing an occupied child is a different operation. Its interface should make the displaced ownership visible:

replace_left(parent, replacement) -> previous subtree

Silently overwriting the link leaks the previous subtree. Silently destroying it may surprise a caller that expected to keep it. Returning it forces the ownership decision into the open.

A low-level binary-node API normally cannot prove that a proposed child is not already elsewhere in the tree. It also cannot cheaply prove that attaching it would not create a cycle. A tree object can provide stronger protection by tracking membership or parent links; otherwise these facts must be documented preconditions.

Parent Links

Adding parent makes upward navigation and node depth queries convenient:

typedef struct ParentNode {
    int value;
    struct ParentNode *parent;
    struct ParentNode *left;
    struct ParentNode *right;
} ParentNode;

The stronger invariant is bidirectional:

root->parent == NULL
p->left  == c implies c->parent == p
p->right == c implies c->parent == p
every non-root node is one of its parent's children

Now attachment changes two links, and detachment clears two links. An assertion should check both views after every update. If an operation updates only parent->left, downward traversal works while upward traversal follows stale state—an especially confusing partial failure.

Parent links can reject cycles locally. Before attaching child beneath parent, walk from parent toward the root. If that walk reaches child, the proposed link would make child its own ancestor. The check costs O(depth(parent)); it buys a safer public editing interface.

Remember that a node’s value is not its identity. Two different nodes may both contain 7. A pointer, an arena index, or an explicit unique ID identifies the node itself. Searches by value may return one match; editing APIs that require an exact node should accept identity, not assume values are unique.

Parent pointers are non-owning back-links. Recursive destruction follows children only. Following both child and parent links during destruction would revisit nodes and can recurse forever.

Tree Cloning

A shallow structure copy duplicates pointers and creates shared ownership:

TreeNode copy = *root; /* copy.left and root->left are the same pointer */

Destroying both apparent trees would then free the same children twice. A true clone creates a fresh node for every source node while preserving shape and values.

Allocation may fail after only part of the clone exists. The recursive routine below either returns a complete independent clone or destroys the partial result and reports failure. The destination is published only on success.

static bool tree_clone(const TreeNode *source, TreeNode **out) {
    if (out == NULL) {
        return false;
    }
    if (source == NULL) {
        *out = NULL;
        return true;
    }

    TreeNode *copy = malloc(sizeof(TreeNode));
    if (copy == NULL) {
        return false;
    }
    copy->value = source->value;
    copy->left = NULL;
    copy->right = NULL;

    if (!tree_clone(source->left, &copy->left) ||
        !tree_clone(source->right, &copy->right)) {
        freeTree(copy);
        return false;
    }

    *out = copy;
    return true;
}

There is a subtle contract detail: on failure, this version does not modify *out. A caller should therefore use a temporary:

TreeNode *clone = NULL;
if (!tree_clone(original, &clone)) {
    /* original is unchanged; clone still has its previous value */
}

The total successful work and extra allocation are Theta(n). The recursive call depth is O(h), so an adversarial chain may still require an iterative version.

Shape Encoding

Values in preorder do not generally encode a binary tree’s shape. These two trees both have preorder A B:

    A          A
   /            \
  B              B

Record every absent child position with a null marker. Preorder serialization then follows this grammar:

tree := # | value tree tree

For the tree

        8
       / \
      3   10
       \
        6

the token sequence is:

8 3 # 6 # # 10 # #

Read it slowly:

1. 8 creates the root.
2. 3 begins the left subtree of 8.
3. # says 3 has no left child.
4. 6 begins the right subtree of 3.
5. two # tokens finish leaf 6.
6. 10 begins the right subtree of 8.
7. two final # tokens finish leaf 10.

Every non-null token consumes exactly two following subtree encodings. A decoder should reject premature end-of-input, an invalid value token, extra tokens after one complete tree, and impossible resource sizes. If parsing or allocation fails halfway, destroy the partial subtree before returning.

Text encoding also needs a value format. If values may contain spaces or the marker character, use length-prefixed fields or escaping rather than ambiguous token splitting. For untrusted input, limit node count and depth before allocating without bound.

For a non-empty binary tree with n nodes, this encoding contains n + 1 null markers and 2n + 1 total tokens. That count is a useful validation check, although matching the count alone does not prove that the token order is grammatical.

Traversal Frames

Recursive traversal stores unfinished work in call frames. Making that state explicit explains iterative traversal and avoids relying on the call stack.

For postorder, a stack entry needs both a node and a phase:

phase 0: left subtree has not started
phase 1: left is complete; right has not started
phase 2: both are complete; process and pop node

On the tree A(B, C), the state evolves like this:

[(A,0)]
[(A,1), (B,0)]
[(A,1), (B,1)]          B has no left child
[(A,1), (B,2)]          B has no right child
[(A,1)]                 process B
[(A,2), (C,0)]
...
[(A,2)]                 process C
[]                      process A

The phases are the program counter that recursion normally hides. Preorder can often push right then left without phases because a node is processed immediately. Inorder needs to remember whether its left subtree has completed. Postorder needs to distinguish both completed-child states.

An iterator keeps this explicit state between calls. next() advances only until it can yield one node, then pauses with the remaining frames intact. Its storage is O(h), and a full iteration remains Theta(n). Decide what mutation does to an active iterator: forbid it, invalidate the iterator using a version counter, or design a more complicated stable-cursor contract.

Arena Storage

Separate allocation is not mandatory. Nodes can live in a growable array and refer to children by indices:

typedef struct {
    int value;
    size_t left;
    size_t right;
} ArenaNode;

Use a sentinel such as SIZE_MAX for no child. Indices survive relocation of the backing array, unlike raw pointers into it, and serialization becomes simpler. Iterating all nodes benefits from locality and cleanup can release the whole arena at once.

The tradeoff is reclamation. Removing one subtree creates unused slots unless the arena maintains a free list. Compacting the arena changes indices and therefore invalidates external node handles. An arena is attractive when trees are built in batches, retained together, and destroyed together; independently lived nodes favor separate allocations or a pool with stable handles.

Tree Hazards

Confusing types

Full, complete, perfect, balanced, and binary describe different properties. A complete tree need not be perfect; a full tree need not be balanced.

Mixing height conventions

If empty height is -1, a leaf has height 0. If empty height is 0, height may count nodes instead. State the convention before using formulas.

Sharing owned subtrees

Two parents pointing to one owned node create a DAG and cause duplicate traversal or double release. Shared substructure needs reference counting, tracing ownership, or a non-owning graph representation.

Orphaning a subtree

Overwriting a child link without returning or destroying the former subtree leaks every node below it.

Recursive depth

A structurally valid skewed tree can overflow the call stack during recursive traversal. Use an explicit stack or constrain height when inputs may be adversarial.

Incomplete serialization

Preorder values alone do not uniquely reconstruct an arbitrary binary tree. Include null markers or combine traversal orders with unique-value assumptions.

Accidental quadratic work

Computing height separately at every node revisits subtrees repeatedly. Return several measurements from one postorder pass when they are needed together.

Binary-Tree Validation

Test distinct shapes rather than only distinct values:

1. empty tree;
2. single leaf;
3. root with only a left child;
4. root with only a right child;
5. full but imperfect tree;
6. complete but imperfect tree;
7. left- and right-skewed trees;
8. maximum expected depth;
9. expression errors such as missing operands or division by zero;
10. construction failure after only part of a tree exists.

Verify traversal sequences, counts, heights, ownership cleanup, and shape invariants independently.

Tree Essentials

• A rooted tree gives every non-root node exactly one parent and one route from the root.
• Depth measures distance from the root; height measures the longest descent to a leaf.
• General, binary, full, complete, perfect, balanced, and skewed trees describe different structural constraints.
• Linked nodes support arbitrary shapes; arrays are especially effective for complete binary trees.
• Parent arrays favor upward navigation; child lists favor downward navigation.
• Preorder, inorder, postorder, and level order process the same nodes in different structural orders.
• Recursive measurements follow directly from the tree’s recursive definition.
• Expression and decision trees attach domain meaning to internal nodes and leaves.
• Unique ownership prevents unreachable subtrees and double release.

Tree Problems

Terminology Questions

1. Distinguish depth, height, level, degree, and width.
2. Give one tree that is full but not complete and one that is complete but not full.
3. Why is inorder not a natural traversal for a general tree?
4. State the ownership invariant of a linked binary tree.

Shape Traces

5. For the running traversal tree, record preorder, inorder, postorder, and level order after adding node K as the right child of H.
6. Compute depth, height, degree, and subtree size for every node in the opening general tree.
7. Encode the opening general tree as a parent array, child lists, and left-child right-sibling links.
8. Map a complete tree with eleven nodes into array indices and derive every parent index.

Structural Failures

9. Find the leaf-count bug in code that tests only node->left == NULL.
10. Explain how replacing parent->left can leak a subtree.
11. Construct a shared-child shape that makes recursive destruction free one node twice.
12. Diagnose serialization that cannot distinguish a left-only child from a right-only child.

Tree Implementations

13. Add treeSum, treeContains, and treeWidth to the full program.
14. Implement iterative preorder and postorder with explicit stacks.
15. Serialize a binary tree in preorder with null markers and deserialize it with allocation-failure cleanup.
16. Implement a general tree with dynamic child arrays and checked attachment/detachment.
17. Convert a general child-list tree to left-child right-sibling representation.

Representation Choices

18. Choose a representation for a read-only filesystem snapshot dominated by parent-path queries.
19. Design an API that transfers subtree ownership safely between two trees.
20. Decide whether an organizational chart with a person reporting to two managers is a tree, then choose a suitable structure.
21. Compare linked and sequential storage for a nearly complete binary tree updated only at its final level.

Measurements and Iterators

22. Compute node count, leaf count, height, and balance status in one postorder traversal.
23. Reconstruct a binary tree from preorder and inorder sequences with unique values.
24. Build an iterator that yields inorder values without recursion and with O(h) state.