11. Trees

🧸 ELI5: A tree is your family tree. You (the root) have parents, they have parents (grandparents), and so on. Or flip it: you have children, they might have children. Everyone is connected, but there's exactly one path from you to any relative — no loops.

🌍 Real life: Folders and subfolders on your computer (Documents > Photos > Vacation > Beach.jpg). A company's org chart (CEO → VPs → Managers → Employees). The <div> structure of a webpage (HTML DOM).

📝 Pseudocode:

node = { value, children[] }

function printTree(node, depth=0):
    print(indent(depth) + node.value)
    for child in node.children:
        printTree(child, depth + 1)

🐹 Go:

package main

import (
	"fmt"
	"strings"
)

type TreeNode struct {
	Name     string
	Children []*TreeNode
}

func printTree(node *TreeNode, depth int) {
	fmt.Println(strings.Repeat("  ", depth) + node.Name)
	for _, child := range node.Children {
		printTree(child, depth+1)
	}
}

func main() {
	grandpa := &TreeNode{Name: "Grandpa"}
	dad := &TreeNode{Name: "Dad"}
	uncle := &TreeNode{Name: "Uncle"}
	me := &TreeNode{Name: "Me"}

	grandpa.Children = []*TreeNode{dad, uncle}
	dad.Children = []*TreeNode{me}

	printTree(grandpa, 0)
	// Grandpa
	//   Dad
	//     Me
	//   Uncle
}

🇨 C (children stored as a realloc-grown array of pointers — Section 16.1's dynamic-array trick, applied per-node):

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

typedef struct TreeNode {
    char name[32];
    struct TreeNode **children;
    int   num_children;
} TreeNode;

TreeNode *tree_new(const char *name) {
    TreeNode *n = calloc(1, sizeof(TreeNode));
    strncpy(n->name, name, sizeof n->name - 1);
    return n;
}

void tree_add_child(TreeNode *parent, TreeNode *child) {
    parent->children = realloc(parent->children,
                                (size_t)(parent->num_children + 1) * sizeof(TreeNode *));
    parent->children[parent->num_children++] = child;
}

void print_tree(TreeNode *node, int depth) {
    for (int i = 0; i < depth; i++) printf("  ");
    printf("%s\n", node->name);
    for (int i = 0; i < node->num_children; i++) print_tree(node->children[i], depth + 1);
}

void tree_free(TreeNode *node) {
    for (int i = 0; i < node->num_children; i++) tree_free(node->children[i]);
    free(node->children);
    free(node);
}

int main(void) {
    TreeNode *grandpa = tree_new("Grandpa");
    TreeNode *dad = tree_new("Dad");
    TreeNode *uncle = tree_new("Uncle");
    TreeNode *me = tree_new("Me");

    tree_add_child(grandpa, dad);
    tree_add_child(grandpa, uncle);
    tree_add_child(dad, me);

    print_tree(grandpa, 0);
    // Grandpa / Dad / Me / Uncle
    tree_free(grandpa);
    return 0;
}

⏱️ Complexity: Traversing every node = O(n). Height of a balanced tree with n nodes = O(log n).