PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

Rare
 0/11

Introduction to Tree Algorithms

Authors: Nathan Chen, Siyong Huang

Introducing a special type of graph: trees.

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 NN nodes and N1N-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 11
    • 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 11
    • Definition 2: Only one node has degree greater than 22
  • 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 nn is the first node along the path from nn 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-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 nn are the set of nodes that have nn 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++

1#include <bits/stdc++.h>
2using namespace std;
3
4const int SZ = 2e5;
5
6vector<int> children[SZ];
7int subtree_size[SZ], depth[SZ];
8
9void dfs_size(int node) {
10 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.

1import java.io.*;
2import java.util.*;
3
4public class Subordinates
5{
6 static InputReader in = new InputReader(System.in);
7 static PrintWriter out = new PrintWriter(System.out);
8
9 public static final int MN = 200020;
10

Problems

StatusSourceProblem NameDifficultyTagsSolution
CFVery Easy
Show Tags

Tree, DFS

Check CF
CFEasy
Show Tags

Tree, DFS

Check CF
SilverEasy
Show Tags

DFS

External Sol
IOIEasy
CSESNormal
Show Tags

Tree, DFS

CPH 14.2
CSESNormal
Show Tags

Tree, DFS

CPH 14.2
CSESNormal
Show Tags

Tree, DFS

View Solution
CCCNormal
Show Tags

Tree, DFS

SilverNormalExternal Sol
CFHard
Show Tags

DFS

Wizard's Tour

Try solving this problem on a tree first!

Module Progress:

Give Us Feedback on Introduction to Tree Algorithms!

PrevNext