Skip to content
CCC Python Course

Trees I: rooting, parent/order arrays, pruning and diameter

Stage
5
Module
M5.8
Lessons
1

In this module

  • Distinguish trees from general graphs and identify their properties.
  • Root a tree at a node and compute parent and depth arrays.
  • Build order arrays and perform tree traversals.
  • Compute tree diameter using two BFS passes.
  • Prune leaves iteratively and compute subtree aggregates.

Before this module

M4.13BFS and flood fill (iterative)M5.7Iterative DFS and recursion elimination

Lessons

  1. 1Trees, rooting and basic properties

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2016 S3
    Phonomenal Reviews (opens on DMOJ in a new tab) DMOJ

    Find which subtrees to keep and minimize the total edge count.

    Why DMOJ: An older tree problem, solvable with the traversal and pruning techniques in this module, that still makes good practice.

  2. 2025 S4
    Floor is Lava (opens on WMOJ in a new tab) WMOJ

    A tree-shaped special case is worth partial credit before the full graph problem.