A tree is a hierarchical data structure used to organize data with parent–child relationships.
Formally, a (rooted) tree is a connected, acyclic graph with a designated root node.
Example:
A
/ | \
B C D
/ \
E F
From this example we define:
- node: an individual element that stores data (e.g.,
A, B, …, F)
- root: the unique top-level node. A tree has exactly one root.
- edge: a connection between two nodes.
- parent / child: if there is an edge from node
X to node Y, then X is the parent and Y is the child.
- leaf: a node with no children (e.g.,
B, D, E, F)
Two important structural properties:
- Every node except the root has exactly one parent.
- There is exactly one simple path between any two nodes (equivalently: trees contain no cycles).
Depth-First Search (DFS)
Depth-First Search (DFS) is an algorithm for traversing or searching a tree.
Starting from the root:
- Explore one branch as deeply as possible.
- When you reach a node with no unvisited children, backtrack.
- Continue until the target is found or all nodes are visited.
class Node:
def __init__(self, value):
self.value = value
self.children = []
def __repr__(self):
return f"Node({self.value!r})"
class Tree:
def __init__(self, root):
self.root = root
def dfs(self, target):
"""
Depth-first search for a target value.
Returns the matching Node if found, else None.
"""
return self._dfs(self.root, target)
def _dfs(self, node, target):
if node.value == target:
return node
for child in node.children:
result = self._dfs(child, target)
if result is not None:
return result
return None
# Build the example tree:
#
# A
# / | \
# B C D
# / \
# E F
A = Node("A")
B = Node("B")
C = Node("C")
D = Node("D")
E = Node("E")
F = Node("F")
A.children = [B, C, D]
C.children = [E, F]
tree = Tree(A)
print(tree.dfs("E")) # Node('E')
print(tree.dfs("Z")) # None