Binary Tree Depth (Recursion/Level Traversal)

Tree structures represent hierarchical data with recurisve properties. For practical use, a struct with left and right pointers (or indices) to track child nodes suffices.

Problem: Binary Tree Depth

This problem focuses on binary tree storage and depth calculation via recursion (or level traversal).

Binary Tree Storage: Each node has two children. Use a struct to store left and right child indices.

struct Node {
    int left, right;
};
Node tree[1000005];

Recursive Depth Calculation: Start from the root. For each node, the depth is 1 plus the maximum depth of its left or right subtree. Leaf nodes (no children) return 0.

int maxDepth(int nodeId) {
    if (nodeId == 0) return 0;
    return 1 + max(maxDepth(tree[nodeId].left), maxDepth(tree[nodeId].right));
}

Full Code:

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int left, right;
} tree[1000005];

int maxDepth(int id) {
    if (id == 0) return 0;
    return 1 + max(maxDepth(tree[id].left), maxDepth(tree[id].right));
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> tree[i].left >> tree[i].right;
    }
    cout << maxDepth(1) << endl;
}

American Ancestry (Pre/In/Post-order Traversal)

Pre-order, in-order, and post-order traversals are depth-first search (DFS) methods for binary trees, differing only in node visit order.

Problem: Reconstruct Tree from Pre-order and In-order

Given pre-order (root-first) and in-order (left-root-right) traversals, reconstruct the tree and output post-order.

Approach:

• Pre-order's first node is the root.
• In-order splits into left/right subtrees at the root.
• Recursively build subtrees.

Code:

#include <iostream>
#include <string>
#include <map>
using namespace std;

struct TreeNode {
    char val;
    TreeNode *left, *right;
    TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(string& pre, map<char, int>& inMap, int s0, int e0, int s1) {
    if (s0 > e0) return nullptr;
    char rootVal = pre[s1];
    int rootIdx = inMap[rootVal];
    int leftLen = rootIdx - s0;
    TreeNode* root = new TreeNode(rootVal);
    root->left = buildTree(pre, inMap, s0, rootIdx - 1, s1 + 1);
    root->right = buildTree(pre, inMap, rootIdx + 1, e0, s1 + 1 + leftLen);
    return root;
}

void postOrder(TreeNode* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val;
}

int main() {
    string pre, in;
    cin >> in >> pre;
    map<char, int> inMap;
    for (int i = 0; i < in.size(); ++i) {
        inMap[in[i]] = i;
    }
    TreeNode* root = buildTree(pre, inMap, 0, in.size() - 1, 0);
    postOrder(root);
}

Traversal Problem (Pre/Post-order)

When only pre-order and post-order are given, the tree structure may not be unique. This is because a node with one child can be left or right, leading to ambiguity. The number of distinct trees is (2^k), where (k) is the number of such nodes.

Code:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string pre, post;
    cin >> pre >> post;
    int count = 1;
    for (int i = 0; i < pre.size() - 1; ++i) {
        for (int j = 0; j < post.size(); ++j) {
            if (pre[i] == post[j] && pre[i+1] == post[j-1]) {
                count *= 2;
            }
        }
    }
    cout << count << endl;
}

Find Preorder Sequence (Post/In-order)

Givan post-order (root is last) and in-order, reconstruct pre-order (root-first).

Approach:

1. Post-order's last node is the root.
2. Split in-order at the root into left/right subtrees.
3. Recursively process subtrees.

Code:

#include <iostream>
#include <string>
using namespace std;

void preorder(string in, string post) {
    if (in.empty()) return;
    char root = post.back();
    cout << root;
    int rootIdx = in.find(root);
    string leftIn = in.substr(0, rootIdx);
    string rightIn = in.substr(rootIdx + 1);
    string leftPost = post.substr(0, leftIn.size());
    string rightPost = post.substr(leftIn.size(), rightIn.size());
    preorder(leftIn, leftPost);
    preorder(rightIn, rightPost);
}

int main() {
    string in, post;
    cin >> in >> post;
    preorder(in, post);
}

Simplified Binary Tree (Binary Search Tree)

Binary Search Trees (BSTs) have O(log n) time for search/insert/delete, but can degenerate to O(n) (e.g., a linked list). Balanced BSTs (like AVL, Red-Black) are preferred, but BSTs are a foundation.

BST Operations:

• Insert: Find the correct position (left for smaller, right for larger) and add the node.
• Predecessor/Successor: Find the largest smaller (predecessor) or smallest larger (successor) node.
• Rank Queries: Find the number of nodes less than a value (rank) or the value at a given rank.

Code (Insert Example):

struct BSTNode {
    int val, cnt, size;
    BSTNode *left, *right;
    BSTNode(int v) : val(v), cnt(1), size(1), left(nullptr), right(nullptr) {}
};

void insert(BSTNode*& root, int v) {
    if (!root) {
        root = new BSTNode(v);
        return;
    }
    root->size++;
    if (v == root->val) {
        root->cnt++;
        return;
    }
    if (v < root->val) {
        insert(root->left, v);
    } else {
        insert(root->right, v);
    }
}

Hospital Setup (BFS)

Calculate the minimum total distance from all nodes to a root (hospital). Use BFS for each node as root and find the minimum sum.

Code:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 105;
bool graph[MAXN][MAXN] = {false};
int value[MAXN] = {0};
bool visited[MAXN] = {false};

struct Node {
    int id, dist;
    Node(int i, int d) : id(i), dist(d) {}
};

int bfs(int root, int n) {
    memset(visited, 0, sizeof(visited));
    queue<Node> q;
    q.push(Node(root, 0));
    visited[root] = true;
    int total = 0;
    while (!q.empty()) {
        Node curr = q.front();
        q.pop();
        for (int i = 1; i <= n; ++i) {
            if (graph[curr.id][i] && !visited[i]) {
                visited[i] = true;
                int newDist = curr.dist + 1;
                total += value[i] * newDist;
                q.push(Node(i, newDist));
            }
        }
    }
    return total;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int w, u, v;
        cin >> w >> u >> v;
        value[i] = w;
        if (u) graph[i][u] = graph[u][i] = true;
        if (v) graph[i][v] = graph[v][i] = true;
    }
    int minDist = 1e9;
    for (int i = 1; i <= n; ++i) {
        minDist = min(minDist, bfs(i, n));
    }
    cout << minDist << endl;
}

Binary Tree Problem (Floyd Algorithm)

Trees are acyclic, connected graphs. Use Floyd-Warshall to compute all-pairs shortest paths (distance between any two nodes).

Code:

#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 0x7fffffff / 4;
int dist[105][105];
int levelCount[105] = {0};

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = (i == j) ? 0 : INF;
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        dist[u][v] = 1;
        dist[v][u] = 2; // Example weights
    }
    // Floyd-Warshall
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    int maxDepth = 0;
    for (int i = 1; i <= n; ++i) {
        maxDepth = max(maxDepth, dist[1][i]);
        levelCount[dist[1][i]]++;
    }
    int maxWidth = 0;
    for (int i = 1; i <= maxDepth; ++i) {
        maxWidth = max(maxWidth, levelCount[i]);
    }
    int u, v;
    cin >> u >> v;
    cout << maxDepth + 1 << endl; // Depth (root is level 1)
    cout << maxWidth << endl;
    cout << dist[u][v] << endl;
}

Lowest Common Ancestor (LCA)

The LCA of two nodes is the deepest node that is an ancestor of both. Using recursion:

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
    TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
    if (!leftLCA) return rightLCA;
    if (!rightLCA) return leftLCA;
    return root;
}