Trees

🏢 Think of a company org chart

The CEO is at the top. Under the CEO are VPs. Under each VP are managers. Under each manager are engineers. This hierarchy is exactly a tree. The CEO is the root. Engineers with no subordinates are leaves.

#include <stdio.h>
#include <stdlib.h>
 
struct TreeNode {
    int data;
    struct TreeNode *left;   /* pointer to left child */
    struct TreeNode *right;  /* pointer to right child */
};
typedef struct TreeNode TreeNode;
 
/* create a new node with given value */
TreeNode* createNode(int value) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data  = value;
    node->left  = NULL;  /* no left child yet */
    node->right = NULL;  /* no right child yet */
    return node;
}
 
int main() {
    /* build this tree manually:
           1
          / \
         2   3
        / \
       4   5
    */
    TreeNode *root = createNode(1);
    root->left     = createNode(2);
    root->right    = createNode(3);
    root->left->left  = createNode(4);
    root->left->right = createNode(5);
 
    /* access nodes */
    printf("Root:         %d\n", root->data);           /* 1 */
    printf("Left child:   %d\n", root->left->data);     /* 2 */
    printf("Right child:  %d\n", root->right->data);    /* 3 */
    printf("Left->Left:   %d\n", root->left->left->data); /* 4 */
 
    return 0;
}

void inorder(TreeNode *root) {
    if (root == NULL) return;  /* base case: empty subtree */
 
    inorder(root->left);         /* 1. visit left subtree */
    printf("%d ", root->data);   /* 2. print current node */
    inorder(root->right);        /* 3. visit right subtree */
}
 
/* inorder(root) → prints: 4 2 5 1 6 3 7 */

void preorder(TreeNode *root) {
    if (root == NULL) return;
 
    printf("%d ", root->data);   /* 1. print current node FIRST */
    preorder(root->left);        /* 2. visit left subtree */
    preorder(root->right);       /* 3. visit right subtree */
}
 
/* preorder(root) → prints: 1 2 4 5 3 6 7 */

void postorder(TreeNode *root) {
    if (root == NULL) return;
 
    postorder(root->left);       /* 1. visit left subtree */
    postorder(root->right);      /* 2. visit right subtree */
    printf("%d ", root->data);   /* 3. print current node LAST */
}
 
/* postorder(root) → prints: 4 5 2 6 7 3 1 */
 
/* deleting a tree safely — must use postorder */
void deleteTree(TreeNode *root) {
    if (root == NULL) return;
    deleteTree(root->left);   /* free children first */
    deleteTree(root->right);
    free(root);                /* then free the parent */
}

#include <stdio.h>
#include <stdlib.h>
 
/* simple queue using array for level order */
#define QMAX 100
 
void levelOrder(TreeNode *root) {
    if (root == NULL) return;
 
    TreeNode *queue[QMAX];
    int front = 0, rear = 0;
 
    queue[rear++] = root;  /* enqueue root */
 
    while (front < rear) {
        TreeNode *current = queue[front++];  /* dequeue */
 
        printf("%d ", current->data);  /* visit current node */
 
        /* enqueue left child if it exists */
        if (current->left != NULL) {
            queue[rear++] = current->left;
        }
        /* enqueue right child if it exists */
        if (current->right != NULL) {
            queue[rear++] = current->right;
        }
    }
}
 
/* levelOrder(root) → prints: 1 2 3 4 5 6 7 */

/* Height = longest path from root to any leaf (measured in edges) */
int height(TreeNode *root) {
    if (root == NULL) return -1;  /* empty tree has height -1 */
    /* (use 0 if measuring in nodes, -1 if measuring in edges) */
 
    int leftHeight  = height(root->left);
    int rightHeight = height(root->right);
 
    /* height = 1 + the taller of the two subtrees */
    int taller = leftHeight > rightHeight ? leftHeight : rightHeight;
    return 1 + taller;
}
 
/* Count = total number of nodes in the tree */
int countNodes(TreeNode *root) {
    if (root == NULL) return 0;  /* empty tree has 0 nodes */
 
    return 1 + countNodes(root->left) + countNodes(root->right);
    /* 1 for current node + all nodes in left + all nodes in right */
}
 
/* Count only leaf nodes (nodes with no children) */
int countLeaves(TreeNode *root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;  /* it is a leaf */
    return countLeaves(root->left) + countLeaves(root->right);
}
 
int main() {
    /* build our example tree */
    TreeNode *root = createNode(1);
    root->left     = createNode(2);
    root->right    = createNode(3);
    root->left->left  = createNode(4);
    root->left->right = createNode(5);
    root->right->left  = createNode(6);
    root->right->right = createNode(7);
 
    printf("Height:      %d\n", height(root));      /* 2 */
    printf("Total nodes: %d\n", countNodes(root));  /* 7 */
    printf("Leaf nodes:  %d\n", countLeaves(root)); /* 4 */
 
    return 0;
}