Extracting Nodes at a Specific Depth in a Complete Binary Tree

When processing a copmlete binary tree with sequentially provided nodes, an array-based representation provides direct mathematical access to child indices. By enforcing 1-based indexing, the left descendant of any element at position i is located at 2 * i, and the right descendant at 2 * i + 1. This mapping removes the overhead of explicit pointer allocations.

To isolate all values residing at a target depth, a breadth-first search (BFS) systematically explores the structure layer by layer. Each visited index records its current traversal depth. When the algorithm encounters indices matching the requested level, their associated values are appended to a dynamic collection. Buffering results before printing guarantees precise control over delimiter placement, eliminating trailing spaces.

#include <cstdio>
#include <queue>
#include <vector>

const int MAX_NODES = 1010;

struct TreeElement {
    int val;
    int lvl;
} tree[MAX_NODES];

int node_count, query_depth;
std::vector<int> level_nodes;

void traverse_bfs(int start_idx) {
    std::queue<int> q;
    tree[start_idx].lvl = 1;
    q.push(start_idx);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        if (tree[curr].lvl == query_depth) {
            level_nodes.push_back(tree[curr].val);
        }

        int left_child = curr * 2;
        int right_child = curr * 2 + 1;

        if (left_child <= node_count) {
            tree[left_child].lvl = tree[curr].lvl + 1;
            q.push(left_child);
        }
        if (right_child <= node_count) {
            tree[right_child].lvl = tree[curr].lvl + 1;
            q.push(right_child);
        }
    }
}

int main() {
    while (scanf("%d", &node_count) == 1 && node_count != 0) {
        for (int i = 1; i <= node_count; ++i) {
            scanf("%d", &tree[i].val);
        }
        scanf("%d", &query_depth);

        level_nodes.clear();
        traverse_bfs(1);

        if (level_nodes.empty()) {
            printf("EMPTY\n");
        } else {
            for (size_t i = 0; i < level_nodes.size(); ++i) {
                printf("%d%c", level_nodes[i], (i == level_nodes.size() - 1) ? '\n' : ' ');
            }
        }
    }
    return 0;
}

Calculating the Height of a General Tree

Arbitrary trees lack the predictable indexing of complete binary trees, necessitating an adjacency list to map parent-child relationships dynamically. Because input edge ordering does not guarantee sequential layer progression, assuming the final processed node holds the maximum depth is incorrect. The tree height must be evaluated continuously during traversal.

A BFS implementation initializes the root at depth 1 and propagates incremented depth values to all connected descendents. As each node is dequeued, a global tracker updates whenever the current node's depth exceeds the previously recorded maximum. This approach ensures accurate height comuptation independent of node labeling or input sequence. Explicitly clearing adjacency lists and depth trackers between test cases prevents state leakage.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

const int LIMIT = 110;

struct GraphNode {
    int depth;
    std::vector<int> next_nodes;
} nodes[LIMIT];

int total_nodes, max_h;

void compute_height(int root) {
    std::queue<int> q;
    nodes[root].depth = 1;
    q.push(root);
    max_h = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        max_h = std::max(max_h, nodes[u].depth);

        for (int v : nodes[u].next_nodes) {
            nodes[v].depth = nodes[u].depth + 1;
            q.push(v);
        }
    }
}

int main() {
    int parent, child;
    while (scanf("%d", &total_nodes) != EOF) {
        for (int i = 0; i <= total_nodes; ++i) {
            nodes[i].next_nodes.clear();
            nodes[i].depth = 0;
        }

        for (int i = 0; i < total_nodes - 1; ++i) {
            scanf("%d %d", &parent, &child);
            nodes[parent].next_nodes.push_back(child);
        }

        max_h = 0;
        if (total_nodes > 0) compute_height(1);
        printf("%d\n", max_h);
    }
    return 0;
}