Tree

A tree is a connected structure with hierarchical relationships and no cycles. It is often described in terms of parents, children, and a root.

Trees make recursion natural because each subtree has the same shape as the whole tree.

Core Idea

In a rooted tree, one node is chosen as the root. Every other node has a parent, and a node may have children. A subtree is the part of the tree below a node.

Many tree algorithms compute something for each subtree and combine child results at the parent.

The absence of cycles is what makes tree reasoning simpler than general graph reasoning. Once the algorithm moves from a parent to a child, it does not need to handle multiple arbitrary paths back to the same node, as long as the parent relationship is respected.

Function Contract

The examples use node to mean either a tree node or None. A None child represents an empty subtree.

count_nodes(node) returns the number of real nodes in the subtree rooted at node. For None, it returns 0. For a real node, it counts the node itself plus all nodes in its child subtrees.

Python Example

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []
 
 
def count_nodes(node):
    total = 1
    for child in node.children:
        total += count_nodes(child)
    return total

The recursive call works because each child is the root of a smaller tree.

Step-by-Step Example

For this tree:

      A
    /   \
   B     C
        /
       D

count_nodes(A) counts A itself, then asks for the size of the subtree rooted at B, then the size of the subtree rooted at C. The call for C asks for the size of the subtree rooted at D.

Each function call has the same meaning: count the nodes in this subtree.

Tree Traversal

Common tree traversals differ by when the current node is processed:

• Preorder: process the node before children.
• Postorder: process children before the node.
• Level order: process by distance from the root using a queue.

Postorder is especially common for tree DP because a parent often needs child answers first.

Complexity

A traversal that visits every node once is O(n) for n nodes. The recursion stack can be O(h), where h is the height of the tree. In the worst case, a very unbalanced tree can have height n.

Common Confusions

A tree is a graph with special structure. Not every graph is a tree.

The word “root” depends on how the tree is viewed. Some problems give an explicit root. Other problems give an undirected tree and the algorithm chooses a root for convenience.

In an undirected tree represented as adjacency lists, recursion must track the parent or visited set. Otherwise the algorithm may walk from child back to parent forever.

When To Use It

Use tree reasoning when data has hierarchy, when a graph is connected and acyclic, or when the problem asks about ancestors, descendants, subtrees, paths, or recursive aggregation.

Do not assume a graph is a tree unless the problem guarantees connectedness and no cycles, or unless those properties have been proven.

The Main Point

A tree is a recursive structure: each child is the root of a smaller tree. Tree algorithms usually work by defining what one subtree answer means.