Tree Data Structures

TL;DR

Tree data structures help organize data hierarchically, like an upside-down tree, where each node can have multiple children but only one parent. They're fundamental for efficient searching, sorting, and storing information that has a natural hierarchy. Understanding trees is key for more advanced topics like binary search trees and graph algorithms.

1. The Mental Model

Imagine a family tree or a company's organizational chart. You have a main person at the top (the CEO or oldest ancestor), and then branches connecting to their direct reports or children, and so on. That's essentially a tree: a way to represent connections where items branch out from a single point.

2. The Core Material

A tree is a non-linear hierarchical data structure that consists of nodes connected by edges. Each tree has a special node called the root, which has no parent. Every other node has exactly one parent. Nodes without children are called leaves.

Key Terminology

Photo by Lukas Blazek on Pexels

• Node: A fundamental part of the tree, storing data and links to other nodes.
• Root: The topmost node of a tree.
• Parent: A node that has child nodes.
• Child: A node directly connected to another node when moving away from the root.
• Sibling: Nodes that share the same parent.
• Edge: The link connecting two nodes.
• Path: A sequence of nodes and edges connecting one node to another.
• Depth: The number of edges from the root to a node. The root has a depth of 0.
• Height: The maximum depth of any node in the tree. The height of a leaf node is 0.
• Subtree: A portion of a tree that can itself be considered a tree, rooted at one of the original tree's nodes.

Types of Trees (Brief Overview)

Photo by 李聪明ing on Pexels

While there are many types, the most common you'll encounter are:

• General Tree: No restrictions on the number of children a node can have.
• Binary Tree: Each node can have at most two children, typically called the "left child" and "right child."
• Binary Search Tree (BST): A special type of binary tree where for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This property makes searching very efficient.
• AVL Tree: A self-balancing binary search tree. It automatically adjusts itself to maintain a balanced height, preventing worst-case search times.

Why use trees?

Photo by David Kanigan on Pexels

Trees are excellent for:
* Representing hierarchical data (file systems, organizational charts).
* Efficient searching and sorting (Binary Search Trees).
* Parsing expressions (syntax trees in compilers).
* Routing algorithms (network topology).

Here's a look at the basic structure:

graph TD
    A["Root (Level 0)"]
    B["Child 1 (Level 1)"]
    C["Child 2 (Level 1)"]
    D["Grandchild 1 (Level 2)"]
    E["Grandchild 2 (Level 2)"]
    F["Grandchild 3 (Level 2)"]
    G["Leaf Node (Level 2)"]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

    subgraph "Subtree rooted at B"
        B --> D
        B --> E
    end

Tree Traversal

Photo by Markus Winkler on Pexels

To visit every node in a tree, you use traversal methods. For binary trees, the main ones are:

• Inorder Traversal (Left -> Root -> Right): Useful for getting sorted data from a BST.
• Preorder Traversal (Root -> Left -> Right): Useful for copying a tree or getting an expression tree prefix notation.
• Postorder Traversal (Left -> Right -> Root): Useful for deleting a tree or getting an expression tree postfix notation.

Let's look at a simple Python class for a Binary Tree node:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Example usage:
# root = TreeNode(10)
# root.left = TreeNode(5)
# root.right = TreeNode(15)
# root.left.left = TreeNode(2)

3. Worked Example

Let's build a simple Binary Search Tree and perform an inorder traversal.

We want to insert the values [10, 5, 15, 2, 7, 12, 20] into an initially empty BST.

1. Insert 10: Root is 10.
   [10]
2. Insert 5: 5 < 10, so it goes to the left of 10.
   [10 (left: 5)]
3. Insert 15: 15 > 10, so it goes to the right of 10.
   [10 (left: 5, right: 15)]
4. Insert 2: 2 < 10, go left. 2 < 5, go left.
   [10 (left: 5 (left: 2), right: 15)]
5. Insert 7: 7 < 10, go left. 7 > 5, go right.
   [10 (left: 5 (left: 2, right: 7), right: 15)]
6. Insert 12: 12 > 10, go right. 12 < 15, go left.
   [10 (left: 5 (left: 2, right: 7), right: 15 (left: 12))]
7. Insert 20: 20 > 10, go right. 20 > 15, go right.
   [10 (left: 5 (left: 2, right: 7), right: 15 (left: 12, right: 20))]

Now let's perform an Inorder Traversal on this BST: (Left -> Root -> Right)

• Start at root (10). Go left.
• At 5. Go left.
• At 2. No left child. Visit 2. Go right (no right child). Return.
• Back at 5. Visit 5. Go right.
• At 7. No left child. Visit 7. No right child. Return.
• Back at 5. Done with 5. Return.
• Back at 10. Visit 10. Go right.
• At 15. Go left.
• At 12. No left child. Visit 12. No right child. Return.
• Back at 15. Visit 15. Go right.
• At 20. No left child. Visit 20. No right child. Return.
• Back at 15. Done with 15. Return.
• Back at 10. Done with 10. Return.

The inorder traversal sequence is: 2, 5, 7, 10, 12, 15, 20. Notice how it's sorted!

Here's the Python code for the insert and inorder_traversal methods:

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

def insert(root, value):
    if root is None:
        return BSTNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else: # value >= root.value, assuming no duplicates or placing duplicates on right
        root.right = insert(root.right, value)
    return root

def inorder_traversal(root):
    elements = []
    if root:
        elements.extend(inorder_traversal(root.left))
        elements.append(root.value)
        elements.extend(inorder_traversal(root.right))
    return elements

# Building the BST:
bst_root = None
values_to_insert = [10, 5, 15, 2, 7, 12, 20]
for val in values_to_insert:
    bst_root = insert(bst_root, val)

print("Inorder Traversal:", inorder_traversal(bst_root)) # Expected: [2, 5, 7, 10, 12, 15, 20]

4. Key Takeaways

• Trees organize data hierarchically with a single root and branches of child nodes.
• Each node can have multiple children but only one parent (except the root).
• Binary Trees restrict nodes to at most two children, while Binary Search Trees (BSTs) add an ordering rule for efficient searching.
• Tree traversal methods (inorder, preorder, postorder) determine the order in which nodes are visited.
• Inorder traversal of a BST yields elements in sorted order.
• Trees are foundational for efficient data management, especially when order or hierarchy matters.

Common Mistakes to Avoid:
- Forgetting that the root node has no parent, and all other nodes have exactly one parent.
- Confusing parent-child relationships with sibling relationships.
- Not understanding the ordering property of a Binary Search Tree (left < root < right), which is crucial for its efficiency.
- Incorrectly implementing recursive tree traversals, leading to missing nodes or infinite loops.

5. Now Try It

Implement a preorder_traversal function for the BSTNode class from the example. Your function should print the root's value first, then recursively traverse its left subtree, then its right subtree. For the example tree you just built (bst_root), your function should output 10, 5, 2, 7, 15, 12, 20.