Rare
0/13

Introduction to Tree Algorithms

Authors: Nathan Chen, Siyong Huang, Albert Ye

Introducing a special type of graph: trees.

Prerequisites

Focus Problem – read through this problem before continuing!

Trees are generally treated very differently from general graph problems.

Resources

Resources
CPH

traversing tree, diameter

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.

C++

#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

Java

Warning!

Because Java is so slow, an adjacency list using lists/arraylists results in TLE. Instead, the Java sample code will use the Chinese edge representation.

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;


Python

In the Python solution, we need to set recursion limit to $2\times10^5$.

import syssys.setrecursionlimit(200006) # set recursion limitdef 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)	sub[x-1] = ans # 0-index is more convenient for printing	return ans+1 # add the node x itselfN = int(input())

Quiz

How is a preorder traversal found for a binary tree?

Question 1 of 3

Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsConnected Components, Diameter, Tree
SilverEasy
Show TagsConnected Components, Tree
CFEasy
Show TagsTree
SilverEasy
Show TagsConnected Components, Tree
SilverEasy
Show TagsGreedy, Tree
BronzeEasy
Show TagsTree
CSESNormal
Show TagsTree
CSESNormal
Show TagsTree
CSESNormal
Show TagsTree
SilverNormal
Show TagsBipartite, Tree
CSESHard
Show TagsDFS, Spanning Tree
CFHard
Show TagsDFS, Spanning Tree

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!