Introduction to Tree Algorithms

Trees are generally treated very differently from general graph problems.

Resources

Some properties/definitions of trees:

• A graph is a tree iff it is connected and contains $N$ nodes and $N-1$ edges
• A graph is a tree iff every pair of nodes has exactly one simple path between them
• A graph is a tree iff it is connected and does not contain any cycles

General Tree Terminology:

• A leaf of a tree is any node in the tree with degree $1$

  • If the tree is rooted, the root with a single child is not typically considered a leaf, but depending on the problem, this is not always the case
• A star graph has two common definitions. Try to understand what they mean - they typically appear in subtasks.

  • Definition 1: Only one node has degree greater than $1$
  • Definition 2: Only one node has degree greater than $2$
• A forest is a graph such that each connected component is a tree

Rooted Tree Terminology:

• A root of a tree is any node of the tree that is considered to be at the 'top'
• A parent of a node $n$ is the first node along the path from $n$ to the root

  • The root does not have a parent. This is typically done in code by setting the parent of the root to be $-1$.
• The ancestors of a node are its parent and parent's ancestors

  • Typically, a node is considered its own ancestor as well (such as in the subtree definition)
• The subtree of a node $n$ are the set of nodes that have $n$ as an ancestor

  • A node is typically considered to be in its own subtree
  • Note: This is easily confused with subgraph
• The depth, or level, of a node is its distance from the root

Solution - Subordinates

In this problem we are given the parent of each node of a rooted tree, and we want to compute the subtree size for each node. A subtree is composed of a root node and the subtrees of the root's children. Thus, the size of a subtree is one plus the size of the root's childrens' subtrees.

Copy
#include <bits/stdc++.h>
using namespace std;

const int SZ = 2e5;

vector<int> children[SZ];
int subtree_size[SZ], depth[SZ];

void dfs_size(int node) {
	subtree_size[node] = 1;  // This one represents the root of `node's` subtree

Copy
import java.io.*;
import java.util.*;

public class Subordinates {
	static InputReader in = new InputReader(System.in);
	static PrintWriter out = new PrintWriter(System.out);

	public static final int MN = 200020;

	static int N, M, ans;

Copy
import sys

sys.setrecursionlimit(200006)  # set recursion limit


def dfs(x):  # x is the current node
	ans = 0  # stores the number of subordinates
	for e in edges[x]:
		if e != fa[x - 1]:
			ans += dfs(e)

Problems

Quiz