[C/C++] BOJ #1068 - Tree

This problem is about finding the number of leaf nodes after deleting a specific node in a tree.

 

Tree: delete node 1

As shown in the figure above, when a tree is given and, for example, node 1 is deleted, nodes 3 and 4 are also deleted as a result. Only node 2 remains as a leaf node. The task is to count such remaining leaf nodes.

 

pruning

---

Although the difficulty is marked as Silver I, the implementation itself is not very difficult.

I solved this problem using a set-like data structure.  Each node only points to its parent. When a node is to be deleted, its parent value is set to -2 to indicate that it has been deleted. Then, among all nodes, we check which ones are not parents to any other nodes. If a node’s value is referenced by another node, it means it is a parent to at least one node and hence cannot be a leaf node. Eventually, only the leaf nodes will have a value of 0.

To find the leaf nodes, we trace each node’s parent all the way to the topmost ancestor.  If the trace ends at -1, it means the node is still part of the tree, so we count it as a leaf node. If the trace ends at -2, it means the node (or its ancestors) has been deleted, so we skip it.

In terms of algorithmic complexity, tracing each node to determine whether it’s a leaf takes \(O(N)\) time.  The worst-case complexity for tracing up to the top ancestor is \(O(N)\) as well, but this only occurs when there are very few leaf nodes. Therefore, the overall complexity becomes approximately \(O(N \log N)\) in practice. Since the number of nodes is at most 50, the algorithm’s efficiency is not a major concern.

Here is the source code I wrote (for reference only):

//----------------------------------------------------------
//    baekjoon #1068 - Tree
//        - by Aubrey Choi
//        - created at 2019-06-28
//----------------------------------------------------------
#include <stdio.h>

struct Node { int value; int parent; };
int main()
{
    int n, p, k, root, ans = 0;
    static Node nodes[50];
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &p);
        nodes[i].parent = p;
        if(p == -1) root = i; else nodes[p].value++;
    }
    scanf("%d", &k);
    if(nodes[k].parent >= 0) nodes[nodes[k].parent].value--;
    nodes[k].parent = -2;
    for(int i = 0; i < n; i++)
    {
        if(nodes[i].value) continue;
        p = nodes[i].parent;
        while(p >= 0) p = nodes[p].parent;
        if(p == -1) ans++;
    }
    printf("%d\n", ans);
}