Trees: Hierarchical Structures

From connections to hierarchy

Now that you've completed Graphs: Concepts and Operations, Recursion: Principles and Algorithms, and Hashmaps: Efficient Data Retrieval, you're ready for a structure that combines ideas from all three.

A tree stores data in a hierarchy: one starting point branches into smaller subgroups.

You see trees in:

• File systems: folders contain folders and files
• Basketball tournaments: one bracket branches into matchups
• True crime case boards: a main case splits into suspects, timelines, evidence, and leads
• Search systems: decisions narrow down what you're looking for

In this lesson, we'll focus on the mental model, core vocabulary, traversal, and the most famous tree variant: the binary search tree.

A tree is a connected hierarchy

A tree is a non-linear data structure made of nodes connected by edges.

Unlike a general graph, a basic tree has a strict hierarchy:

        A        <- root
      /   \
     B     C     <- children of A
    / \     \
   D   E     F   <- leaves

Key terms:

• Root: the top node; every tree starts here
• Parent: a node directly above another node
• Child: a node directly below another node
• Leaf: a node with no children
• Subtree: any node plus everything below it
• Height: how many edges are on the longest downward path

The big idea: trees make relationships feel like "contains," "belongs to," or "comes after" rather than just "is connected to."

In a tree, which node is called the root?

A tree node stores data and links

In Python, a basic tree node can be represented with a class that stores:

• a value
• a list of children

This is a general tree, meaning each node can have any number of children.

The example below models a small hierarchy like a team roster: one team has position groups, and each group has players.

```python
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

team = TreeNode("City Hoopers")
guards = TreeNode("Guards")
forwards = TreeNode("Forwards")

team.add_child(guards)
team.add_child(forwards)

guards.add_child(TreeNode("Ari"))
guards.add_child(TreeNode("Devin"))
forwards.add_child(TreeNode("Maya"))

print("Root:", team.value)
print("Position groups:", [child.value for child in team.children])
print("Guards:", [child.value for child in guards.children])
```

Traversal means visiting every node

You already saw traversal in graphs. In trees, traversal is usually more structured because each node has clear children.

For a binary tree, each node has at most two children:

• left
• right

Three classic depth-first traversal orders are:

• Pre-order: node, left, right
• In-order: left, node, right
• Post-order: left, right, node

These orders are not random. They answer different questions: "process the boss first," "process sorted values," or "process children before parent."

```python
class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]

root = BinaryNode("A")
root.left = BinaryNode("B")
root.right = BinaryNode("C")
root.left.left = BinaryNode("D")
root.left.right = BinaryNode("E")

print("Pre-order:", preorder(root))
print("In-order:", inorder(root))
print("Post-order:", postorder(root))
```

For a binary search tree, an in-order traversal visits values in ____ order.

A tree built for searching

A binary search tree, or BST, is a binary tree with an ordering rule:

• values smaller than a node go in the left subtree
• values larger than a node go in the right subtree

That rule lets us search by repeatedly choosing left or right, similar to narrowing down suspects in a case file.

If the tree is reasonably balanced, search can be very fast: about O(log n). If the tree becomes a long chain, search can degrade to O(n).

```python
class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left is None:
                self.left = BSTNode(value)
            else:
                self.left.insert(value)
        elif value > self.value:
            if self.right is None:
                self.right = BSTNode(value)
            else:
                self.right.insert(value)

    def contains(self, value):
        if value == self.value:
            return True
        if value < self.value:
            return self.left.contains(value) if self.left else False
        return self.right.contains(value) if self.right else False

root = BSTNode(50)
for score in [30, 70, 20, 40, 60, 80]:
    root.insert(score)

print("Contains 60?", root.contains(60))
print("Contains 25?", root.contains(25))
```

True or false: In a binary search tree with unique values, every value in a node's left subtree is smaller than that node, and every value in its right subtree is larger.

The same values can form very different trees

Tree performance depends heavily on height.

A balanced tree stays short and wide:

      40
    /    \
   20     60
  / \    / \
10  30  50  70

An unbalanced tree can become a chain:

10
  \
   20
     \
      30
        \
         40

Why this matters:

• Searching a balanced BST is roughly O(log n)
• Searching a chain-shaped BST is O(n)
• Insertion can accidentally create a bad shape
• Deletion must preserve the BST ordering rule

Self-balancing trees like AVL trees and red-black trees fix this by rotating nodes after updates. You don't need to implement rotations yet; just remember that shape controls speed.

Which scenario is the best natural fit for a tree structure?

What you should remember

Trees are the course's clearest example of hierarchical structure.

You learned that:

• Trees have roots, parents, children, leaves, subtrees, and height
• A binary tree gives each node at most two children
• Traversals define the order in which nodes are visited
• A BST adds an ordering rule for faster search
• Tree height strongly affects performance
• Balanced trees protect search, insertion, and deletion from becoming too slow

You now have graphs for relationships, recursion for self-similar problems, hashmaps for fast lookup, and trees for hierarchy. In the final lesson, we'll briefly combine these tools to reason through real problem-solving choices.