Binary Tree Fundamentals

Binary trees are fundamental data structures where each node has at most two children. Understanding binary tree operations is essential for technical interviews and practical development.

Storage Methods

Binary trees can be stored using linked structures or sequential arrays. Linked storage uses node structures with left and right child pointers. Sequential storage uses arrays where for any node at index i, its left child is at 2i+1 and right child at 2i+2.

In C++ standard library, containers like map, set, multimap, and multiset use balanced binary search trees as their underlying structure, providing O(log n) time complexity for insertion and deletion operations. However, unordered_map and unordered_set use hash tables instead. Understanding these implementation details is crucial for proper algorithm analysis.

Traversal Categories

Binary tree traversal falls in to two primary categories:

Depth-First Traversal: Explores as deep as possible before backtracking Breadth-First Traversal: Explores level by level

Depth-first traversal includes three variations based on when the root node is processed:

Preorder: Root, Left, Right Inorder: Left, Root, Right Postorder: Left, Right, Root

Breadth-first traversal, also known as level order, visits nodes level by level from left to right.

Recursive Traversal Implementation

Recursive traversal requires defining three key elements: function parameters and return type, termination condition, and single-level logic.

For preorder traversal, the function takes the current node pointer and a result array. The termination condition checks for null nodes. The single-level logic processes the current node, then recursively visits left and right subtrees.

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

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

void collectPreorder(TreeNode* current, int* output, int* position) {
    if (current == NULL) return;
    output[(*position)++] = current->value;
    collectPreorder(current->left, output, position);
    collectPreorder(current->right, output, position);
}

int* preorderTraversal(TreeNode* root, int* resultSize) {
    int* output = (int*)malloc(1000 * sizeof(int));
    *resultSize = 0;
    collectPreorder(root, output, resultSize);
    return output;
}

Inorder traversal moves the processing step between the two recursive calls:

void collectInorder(TreeNode* current, int* output, int* position) {
    if (current == NULL) return;
    collectInorder(current->left, output, position);
    output[(*position)++] = current->value;
    collectInorder(current->right, output, position);
}

Postorder traversal processes the node after both subtrees:

void collectPostorder(TreeNode* current, int* output, int* position) {
    if (current == NULL) return;
    collectPostorder(current->left, output, position);
    collectPostorder(current->right, output, position);
    output[(*position)++] = current->value;
}

Iterative Traversal with Stack

Recursive calls use the call stack implicitly, so we can simulate this behavior using an explicit stack structure. The stack naturally handles the backtracking required for tree traversal.

Preorder Iterative Implementation

For preorder, we push nodes onto the stack and process them immediately. When pushing children, push the right child first so the left child processes first:

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

typedef struct Node {
    TreeNode* treeNode;
    struct Node* next;
} Node;

typedef struct Stack {
    Node* top;
} Stack;

void initStack(Stack* s) {
    s->top = NULL;
}

int isEmpty(Stack* s) {
    return s->top == NULL;
}

void push(Stack* s, TreeNode* node) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->treeNode = node;
    newNode->next = s->top;
    s->top = newNode;
}

TreeNode* pop(Stack* s) {
    if (isEmpty(s)) return NULL;
    Node* temp = s->top;
    TreeNode* result = temp->treeNode;
    s->top = temp->next;
    free(temp);
    return result;
}

int* preorderIterative(TreeNode* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    int* result = (int*)malloc(1000 * sizeof(int));
    *returnSize = 0;
    
    Stack stack;
    initStack(&stack);
    push(&stack, root);
    
    while (!isEmpty(&stack)) {
        TreeNode* current = pop(&stack);
        result[(*returnSize)++] = current->value;
        
        if (current->right) push(&stack, current->right);
        if (current->left) push(&stack, current->left);
    }
    
    return result;
}

Inorder Iterative Implementation

Inorder traversal requires a different approach because visiting and processing nodes occur at different times. We use a pointer to traverse and a stack to track nodes:

int* inorderIterative(TreeNode* root, int* returnSize) {
    int* result = (int*)malloc(100 * sizeof(int));
    int index = 0;
    int top = -1;
    TreeNode** stack = (TreeNode**)malloc(100 * sizeof(TreeNode*));
    
    TreeNode* current = root;
    
    while (current != NULL || top != -1) {
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        result[index++] = current->value;
        current = current->right;
    }
    
    free(stack);
    *returnSize = index;
    return result;
}

Postorder Iterative Implementation

A simple trick for postorder is to perform preorder (root-left-right), then reverse the result to get left-right-root:

int* postorderIterative(TreeNode* root, int* returnSize) {
    TreeNode** stack = (TreeNode**)malloc(100 * sizeof(TreeNode*));
    int top = -1;
    int* result = (int*)malloc(100 * sizeof(int));
    int index = 0;
    
    if (root == NULL) {
        *returnSize = 0;
        return result;
    }
    
    push(stack, &top, root);
    
    while (top != -1) {
        TreeNode* node = pop(stack, &top);
        result[index++] = node->value;
        if (node->left) push(stack, &top, node->left);
        if (node->right) push(stack, &top, node->right);
    }
    
    free(stack);
    
    for (int i = 0, j = index - 1; i < j; i++, j--) {
        int temp = result[i];
        result[i] = result[j];
        result[j] = temp;
    }
    
    *returnSize = index;
    return result;
}

Unified Iterative Approach

A unified approach uses null pointers as markers. When we encounter a null, we pop and process the next node:

int* inorderUnified(TreeNode* root, int* returnSize) {
    TreeNode** stack = (TreeNode**)malloc(200 * sizeof(TreeNode*));
    int top = -1;
    int* result = (int*)malloc(100 * sizeof(int));
    int index = 0;
    
    if (root != NULL) {
        stack[++top] = root;
    }
    
    while (top != -1) {
        TreeNode* node = stack[top];
        if (node != NULL) {
            stack[top] = NULL;
            if (node->right) stack[++top] = node->right;
            stack[++top] = node;
            stack[++top] = NULL;
            if (node->left) stack[++top] = node->left;
        } else {
            top--;
            node = stack[top--];
            result[index++] = node->value;
        }
    }
    
    free(stack);
    *returnSize = index;
    return result;
}

Level Order Traversal

Level order traversal uses a queue (FIFO) to process nodes level by level:

typedef struct Queue {
    TreeNode** data;
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

void enqueue(Queue* q, TreeNode* node) {
    q->data[q->rear++] = node;
}

TreeNode* dequeue(Queue* q) {
    return q->data[q->front++];
}

int isQueueEmpty(Queue* q) {
    return q->front == q->rear;
}

int** levelOrder(TreeNode* root, int* returnSize, int** columnSizes) {
    int** result = (int**)malloc(100 * sizeof(int*));
    *columnSizes = (int*)malloc(100 * sizeof(int));
    *returnSize = 0;
    
    Queue queue;
    initQueue(&queue);
    
    if (root) enqueue(&queue, root);
    
    while (!isQueueEmpty(&queue)) {
        int levelSize = queue.rear - queue.front;
        int* row = (int*)malloc(levelSize * sizeof(int));
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = dequeue(&queue);
            row[i] = node->value;
            if (node->left) enqueue(&queue, node->left);
            if (node->right) enqueue(&queue, node->right);
        }
        result[*returnSize] = row;
        (*columnSizes)[*returnSize] = levelSize;
        (*returnSize)++;
    }
    
    return result;
}

Tree Inversion

Inverting a binary tree swaps each node's left and right children. This works with any traversal order—preorder, postorder, or level order all achieve the same result:

TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) return root;
    
    TreeNode** stack = (TreeNode**)malloc(sizeof(TreeNode*) * 1000);
    int top = -1;
    stack[++top] = root;
    
    while (top > -1) {
        TreeNode* node = stack[top--];
        
        TreeNode* temp = node->left;
        node->left = node->right;
        node->right = temp;
        
        if (node->right) stack[++top] = node->right;
        if (node->left) stack[++top] = node->left;
    }
    
    free(stack);
    return root;
}

Symmetric Tree Check

To check if a tree is symmetric, compare the left subtree with a mirror of the right subtree:

int compareSubtrees(TreeNode* left, TreeNode* right) {
    if (left == NULL && right == NULL) return 1;
    if (left == NULL || right == NULL) return 0;
    if (left->value != right->value) return 0;
    
    return compareSubtrees(left->left, right->right) 
        && compareSubtrees(left->right, right->left);
}

int isSymmetric(TreeNode* root) {
    if (root == NULL) return 1;
    return compareSubtrees(root->left, root->right);
}

An iterative approach using a queue processes node pairs:

int isSymmetricIterative(TreeNode* root) {
    if (root == NULL) return 1;
    
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, root->left);
    enqueue(&queue, root->right);
    
    while (queue.front != queue.rear) {
        TreeNode* left = dequeue(&queue);
        TreeNode* right = dequeue(&queue);
        
        if (!left && !right) continue;
        if (!left || !right || left->value != right->value) return 0;
        
        enqueue(&queue, left->left);
        enqueue(&queue, right->right);
        enqueue(&queue, left->right);
        enqueue(&queue, right->left);
    }
    return 1;
}

Counting Tree Nodes

For a complete binary tree, we can optimize by checking if subtrees are full:

int getDepthLeft(TreeNode* node) {
    int depth = 0;
    while (node) {
        node = node->left;
        depth++;
    }
    return depth;
}

int getDepthRight(TreeNode* node) {
    int depth = 0;
    while (node) {
        node = node->right;
        depth++;
    }
    return depth;
}

int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    
    TreeNode* left = root->left;
    TreeNode* right = root->right;
    int leftDepth = 0, rightDepth = 0;
    
    while (left) {
        left = left->left;
        leftDepth++;
    }
    while (right) {
        right = right->right;
        rightDepth++;
    }
    
    if (leftDepth == rightDepth) {
        return (1 << leftDepth) + countNodes(root->right) - 1;
    }
    
    return countNodes(root->left) + countNodes(root->right) + 1;
}

Balanced Tree Check

A tree is balanced if the height difference between any node's subtrees is at most 1:

int getHeight(TreeNode* node) {
    if (node == NULL) return 0;
    
    int leftHeight = getHeight(node->left);
    if (leftHeight == -1) return -1;
    
    int rightHeight = getHeight(node->right);
    if (rightHeight == -1) return -1;
    
    if (abs(leftHeight - rightHeight) > 1) return -1;
    
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int isBalanced(TreeNode* root) {
    return getHeight(root) != -1;
}

Finding All Paths

To find all root-to-leaf paths, use preorder traversal with backtracking:

void findPaths(TreeNode* node, int* path, int pathLen, char** results, int* resultCount) {
    if (node == NULL) return;
    
    path[pathLen++] = node->value;
    
    if (node->left == NULL && node->right == NULL) {
        char* buffer = (char*)malloc(1000);
        int offset = 0;
        for (int i = 0; i < pathLen; i++) {
            offset += sprintf(buffer + offset, "%d%s", path[i], 
                             i < pathLen - 1 ? "->" : "");
        }
        results[*resultCount] = buffer;
        (*resultCount)++;
    } else {
        if (node->left) findPaths(node->left, path, pathLen, results, resultCount);
        if (node->right) findPaths(node->right, path, pathLen, results, resultCount);
    }
}

char** binaryTreePaths(TreeNode* root, int* returnSize) {
    char** results = (char**)malloc(100 * sizeof(char*));
    *returnSize = 0;
    
    if (root == NULL) return results;
    
    int* path = (int*)malloc(100 * sizeof(int));
    findPaths(root, path, 0, results, returnSize);
    free(path);
    
    return results;
}

Tree Depth Problems

Maximum depth can be found using level order traversal:

int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    
    int depth = 0;
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, root);
    
    while (!isQueueEmpty(&queue)) {
        int levelSize = queue.rear - queue.front;
        depth++;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = dequeue(&queue);
            if (node->left) enqueue(&queue, node->left);
            if (node->right) enqueue(&queue, node->right);
        }
    }
    return depth;
}

Minimum depth is similar but stops when encountering a leaf node:

int minDepth(TreeNode* root) {
    if (root == NULL) return 0;
    
    int depth = 0;
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, root);
    
    while (!isQueueEmpty(&queue)) {
        int levelSize = queue.rear - queue.front;
        depth++;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = dequeue(&queue);
            if (!node->left && !node->right) return depth;
            if (node->left) enqueue(&queue, node->left);
            if (node->right) enqueue(&queue, node->right);
        }
    }
    return depth;
}

Level Average

Computing level averages uses the same level order pattern:

double* averageOfLevels(TreeNode* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    double* result = (double*)malloc(100 * sizeof(double));
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, root);
    *returnSize = 0;
    
    while (!isQueueEmpty(&queue)) {
        int levelSize = queue.rear - queue.front;
        double sum = 0;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = dequeue(&queue);
            sum += node->value;
            if (node->left) enqueue(&queue, node->left);
            if (node->right) enqueue(&queue, node->right);
        }
        result[(*returnSize)++] = sum / levelSize;
    }
    return result;
}

Right Side View

The right side view requires capturing the last node at each level:

int* rightSideView(TreeNode* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    int* result = (int*)malloc(100 * sizeof(int));
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, root);
    *returnSize = 0;
    
    while (!isQueueEmpty(&queue)) {
        int levelSize = queue.rear - queue.front;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = dequeue(&queue);
            if (i == levelSize - 1) {
                result[(*returnSize)++] = node->value;
            }
            if (node->left) enqueue(&queue, node->left);
            if (node->right) enqueue(&queue, node->right);
        }
    }
    return result;
}