Computing Binary Tree Depth

Calculating the maximum depth of a binary tree is a foundational recursive operation. The depth of any node equals one plus the maximum depth of its subtrees. A clean implementation avoids redundant checks by leveraging the base case of a null pointer.

int computeTreeDepth(const BinTree node) {
    if (node == NULL) {
        return 0;
    }
    int leftSubtree = computeTreeDepth(node->Left);
    int rightSubtree = computeTreeDepth(node->Right);
    return 1 + (leftSubtree > rightSubtree ? leftSubtree : rightSubtree);
}

Core Traversal Implementations

Depth-first traversals (preorder, inorder, postorder) differ only in the timing of node visitation relative to recursive calls. Level-order traversal requires a queue to process nodes breadth-first. The following implementations standardize these patterns with explicit boundary handling.

void traverseInorder(const BinTree node) {
    if (node != NULL) {
        traverseInorder(node->Left);
        printf(" %c", node->Data);
        traverseInorder(node->Right);
    }
}

void traversePreorder(const BinTree node) {
    if (node != NULL) {
        printf(" %c", node->Data);
        traversePreorder(node->Left);
        traversePreorder(node->Right);
    }
}

void traversePostorder(const BinTree node) {
    if (node != NULL) {
        traversePostorder(node->Left);
        traversePostorder(node->Right);
        printf(" %c", node->Data);
    }
}

void traverseLevelOrder(const BinTree root) {
    if (root == NULL) return;
    
    const BinTree queue[1024];
    int head = 0, tail = 0;
    queue[tail++] = root;
    
    while (head < tail) {
        const BinTree current = queue[head++];
        printf(" %c", current->Data);
        if (current->Left) queue[tail++] = current->Left;
        if (current->Right) queue[tail++] = current->Right;
    }
}

Extracting Leaf Nodes in Preorder

When isolating leaf nodes while preserving preorder semantics, the visitation check must occur before descending into subtrees. This prevents the traversal from mimicking postorder behavior and ensures leaves are printed exactly when first encountered.

void printLeavesPreorder(const BinTree node) {
    if (node == NULL) return;
    
    if (node->Left == NULL && node->Right == NULL) {
        printf(" %c", node->Data);
        return;
    }
    
    printLeavesPreorder(node->Left);
    printLeavesPreorder(node->Right);
}

Reconstructing Traversal Orders from Inorder and Postorder Sequences

Given an inorder and a postorder sequence, the root is always the last element of the postorder segment. By locating this root in the inorder array, we can partition the sequence into left and right subtrees. Rather than constructing physical nodes, we can directly compute the preorder sequence by printing the root and recursively processing the partitions.

#include <stdio.h>

void generatePreorder(const int inorder[], const int postorder[], int iStart, int iEnd, int pStart, int pEnd) {
    if (iStart > iEnd || pStart > pEnd) return;
    
    const int rootVal = postorder[pEnd];
    printf(" %d", rootVal);
    
    int rootIdx = iStart;
    while (rootIdx <= iEnd && inorder[rootIdx] != rootVal) {
        rootIdx++;
    }
    
    const int leftSize = rootIdx - iStart;
    
    generatePreorder(inorder, postorder, iStart, rootIdx - 1, pStart, pStart + leftSize - 1);
    generatePreorder(inorder, postorder, rootIdx + 1, iEnd, pStart + leftSize, pEnd - 1);
}

int main() {
    int n;
    scanf("%d", &n);
    
    int post[40], in[40];
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    
    printf("Preorder:");
    generatePreorder(in, post, 0, n - 1, 0, n - 1);
    printf("\n");
    return 0;
}

Checking Structural Isomorphism Between Trees

Two trees are isomorphic if one can be transformed into the other by swapping left and right children of any number of nodes. The algorithm identifies root nodes by tracking in-degrees, then recursively compares structures. Child order is normalized during comparison to account for permissible swaps.

#include <stdio.h>

#define MAX_NODES 20

typedef struct {
    char val;
    int left, right;
} Node;

Node forestA[MAX_NODES], forestB[MAX_NODES];
int inDegreeA[MAX_NODES], inDegreeB[MAX_NODES];

int locateRoot(Node trees[], int inDeg[], int count) {
    for (int i = 0; i < count; i++) {
        if (inDeg[i] == 0) return i;
    }
    return -1;
}

int buildTree(Node trees[], int inDeg[], int count) {
    scanf("%d", &count);
    for (int i = 0; i < count; i++) inDeg[i] = 0;
    
    for (int i = 0; i < count; i++) {
        char lChar, rChar;
        scanf(" %c %c %c", &trees[i].val, &lChar, &rChar);
        trees[i].left = (lChar == '-' ? -1 : lChar - '0');
        trees[i].right = (rChar == '-' ? -1 : rChar - '0');
        if (trees[i].left != -1) inDeg[trees[i].left] = 1;
        if (trees[i].right != -1) inDeg[trees[i].right] = 1;
    }
    return locateRoot(trees, inDeg, count);
}

int areIsomorphic(int rootA, int rootB) {
    if (rootA == -1 && rootB == -1) return 1;
    if (rootA == -1 || rootB == -1) return 0;
    if (forestA[rootA].val != forestB[rootB].val) return 0;
    
    int leftA = forestA[rootA].left;
    int rightA = forestA[rootA].right;
    int leftB = forestB[rootB].left;
    int rightB = forestB[rootB].right;
    
    if (leftA == -1 && leftB == -1) {
        return areIsomorphic(rightA, rightB);
    }
    
    if ((leftA != -1 && leftB != -1) && 
        forestA[leftA].val == forestB[leftB].val) {
        return areIsomorphic(leftA, leftB) && areIsomorphic(rightA, rightB);
    }
    
    return areIsomorphic(leftA, rightB) && areIsomorphic(rightA, leftB);
}

int main() {
    int rootA = buildTree(forestA, inDegreeA, 0);
    int rootB = buildTree(forestB, inDegreeB, 0);
    printf("%s\n", areIsomorphic(rootA, rootB) ? "Yes" : "No");
    return 0;
}

Minimizing Merge Costs via Min-Heap Aggregation

The optimal cost to combine a set of weighted segments follows Huffman's principle: repeatedly merge the two smallest available weights and accumulate the result. A min-priority queue efficiently maintains the order of operations, ensuring linear-logarithmic time complexity.

#include <stdio.h>
#include <queue>
#include <vector>

int main() {
    int n;
    scanf("%d", &n);
    
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int i = 0; i < n; i++) {
        int weight;
        scanf("%d", &weight);
        minHeap.push(weight);
    }
    
    int totalCost = 0;
    while (minHeap.size() > 1) {
        int first = minHeap.top(); minHeap.pop();
        int second = minHeap.top(); minHeap.pop();
        
        int combined = first + second;
        totalCost += combined;
        minHeap.push(combined);
    }
    
    printf("%d\n", totalCost);
    return 0;
}

Constructing Complete Binary Search Trees from Sorted Arrays

A complete binary search tree (CBST) maintains the BST property while filling levels left-to-right. When given a sorted sequence, the correct placement of each element coresponds to an in-order traversal of the complete binary tree structure. By simulating an in-order walk over array indices, we can map the sorted values direct into the CBST layout.

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

int sourceValues[1001];
int cbstLayout[1001];
int currentIndex;

void mapInorderPosition(int nodeIndex, int totalNodes) {
    if (nodeIndex > totalNodes) return;
    
    mapInorderPosition(nodeIndex * 2, totalNodes);
    cbstLayout[nodeIndex] = sourceValues[currentIndex++];
    mapInorderPosition(nodeIndex * 2 + 1, totalNodes);
}

int compareInts(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &sourceValues[i]);
    }
    
    qsort(sourceValues, n, sizeof(int), compareInts);
    
    currentIndex = 0;
    mapInorderPosition(1, n);
    
    for (int i = 1; i <= n; i++) {
        printf("%d%c", cbstLayout[i], (i == n ? '\n' : ' '));
    }
    
    return 0;
}