Walking a tree in C

In-order, depth, and freeing: three recursions with the same shape.

#include <stdlib.h>

typedef struct Tree {
    int key;
    struct Tree *left;
    struct Tree *right;
} Tree;

void in_order(const Tree *node, int *out, int *n) {
    if (node == NULL) {
        return;
    }
    in_order(node->left, out, n);
    out[(*n)++] = node->key;
    in_order(node->right, out, n);
}

int depth(const Tree *node) {
    if (node == NULL) {
        return 0;
    }
    int left = depth(node->left);
    int right = depth(node->right);
    return 1 + ((left > right) ? left : right);
}

void tree_free(Tree *node) {
    if (node == NULL) {
        return;
    }
    tree_free(node->left);
    tree_free(node->right);
    free(node);
}

How it works

1. In-order means left subtree, node, right subtree.
2. Depth is one plus the deeper child.
3. Freeing must visit the children before the parent.

Keywords and builtins used here

• NULL
• Tree
• const
• depth
• if
• in_order
• int
• return
• struct
• tree_free
• typedef
• void

The run, in numbers

Lines

34

Characters to type

561

Tokens

191

Three-star pace

105 tpm

At the three-star pace of 105 tokens a minute, this run takes about 109 seconds.

Type this snippet

Step 2 of 4 in Trees, tables & heaps, step 12 of 20 in Data structures & algorithms.

← Previous Next →