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.

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.

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.

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.