Trees

Overview

A tree is a hierarchical data structure that consists of nodes connected by edges. It is widely used for representing hierarchical relationships such as organisational structures, file systems, and decision-making processes. Trees are a specific type of graph without cycles, where one node is designated as the root, and every other node is a descendant of the root.

Structure of a Tree

Root: The topmost node.
Parent: A node with children.
Child: A node with a parent.
Leaf: A node with no children.
Subtree: A portion of the tree that includes a node and its descendants.

Types of Trees

Binary Tree: Each node has at most two children.
Binary Search Tree (BST): A binary tree where the left child contains smaller values, and the right child contains larger values.
Balanced Trees (e.g., AVL Trees): Ensure that the tree remains balanced for efficient operations.
N-ary Tree: Each node can have up to N children.

Implementing Trees

Using Procedural Programming (Arrays or Pointers)

Array Representation (Binary Tree)

Nodes are stored in an array.
For a node at index i:
- Left child: 2*i + 1
- Right child: 2*i + 2
- Parent: (i-1) // 2

lightbulbExample

Example:

# Binary Tree represented as an array
tree = [None] * 7  # Fixed-size tree

def add_to_tree(value, index):
    if index < len(tree):
        tree[index] = value

add_to_tree(10, 0)  # Root
add_to_tree(5, 1)   # Left child of root
add_to_tree(15, 2)  # Right child of root
print(tree)  # Output: [10, 5, 15, None, None, None, None]

Pointers (Binary Tree)

Using nodes with pointers to the left and right children.

lightbulbExample

Example:

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

# Creating nodes
root = Node(10)
root.left = Node(5)
root.right = Node(15)

Using Object-Oriented Programming (OOP)

A class-based implementation makes it easier to manage trees.

lightbulbExample

Example:

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

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
        else:
            self._insert(self.root, value)

    def _insert(self, current, value):
        if value < current.value:
            if current.left:
                self._insert(current.left, value)
            else:
                current.left = TreeNode(value)
        else:
            if current.right:
                self._insert(current.right, value)
            else:
                current.right = TreeNode(value)

Tree Traversal

Traversal involves visiting all the nodes in a tree in a specific order.

Preorder Traversal (Root, Left, Right):

Visit the root, then recursively visit the left and right subtrees.

lightbulbExample

Example:

def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)

Inorder Traversal (Left, Root, Right):

Visit the left subtree, then the root, then the right subtree. Commonly used for BSTs to retrieve sorted data.

lightbulbExample

Example:

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)

Postorder Traversal (Left, Right, Root):

Visit the left and right subtrees first, then the root.

lightbulbExample

Example:

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")

Level-Order Traversal (Breadth-First):

Visit nodes level by level using a queue.

lightbulbExample

Example:

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        current = queue.popleft()
        print(current.value, end=" ")
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)

Adding and Removing Data

Adding Data

In a Binary Search Tree (BST):

Add nodes such that left children < parent and right children > parent.

lightbulbExample

Example:

def insert(node, value):
    if not node:
        return TreeNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

Removing Data

Removing a node requires handling three cases:

Node with no children (leaf): Simply delete the node.
Node with one child: Replace the node with its child.
Node with two children: Replace the node with its in-order successor (smallest node in the right subtree).

lightbulbExample

Example:

def delete_node(root, value):
    if not root:
        return root
    if value < root.value:
        root.left = delete_node(root.left, value)
    elif value > root.value:
        root.right = delete_node(root.right, value)
    else:
        # Node with one or no child
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        # Node with two children
        temp = min_value_node(root.right)
        root.value = temp.value
        root.right = delete_node(root.right, temp.value)
    return root

def min_value_node(node):
    current = node
    while current.left:
        current = current.left
    return current

Note Summary

infoNote

Common Mistakes

Incorrect Traversal Logic:

Skipping nodes or visiting them multiple times.
Confusing preorder, inorder, and postorder traversals.

Not Handling Edge Cases in Removal:

Forgetting to handle nodes with one or no child.
Incorrectly finding the in-order successor.

Misunderstanding BST Properties:

Failing to maintain the BST structure when inserting or deleting nodes.

Null Pointer Errors:

Attempting to access properties of None nodes in procedural or pointer-based implementations.

infoNote

Key Takeaways

Trees are hierarchical structures used to model data with parent-child relationships.
Common types include Binary Trees and Binary Search Trees.
Practice traversal methods like preorder, inorder, postorder, and level-order.
Understand the principles of adding and removing data to ensure proper tree structure.
Focus on reading and writing code to reinforce these concepts.

Trees Simplified Revision Notes for A-Level OCR Computer Science

Trees

Overview

Structure of a Tree

Types of Trees

Implementing Trees

Using Procedural Programming (Arrays or Pointers)

Array Representation (Binary Tree)

Pointers (Binary Tree)

Using Object-Oriented Programming (OOP)

Tree Traversal

Preorder Traversal (Root, Left, Right):

Inorder Traversal (Left, Root, Right):

Postorder Traversal (Left, Right, Root):

Level-Order Traversal (Breadth-First):

Adding and Removing Data

Adding Data

Removing Data

Note Summary

Common Mistakes

Key Takeaways

500K+ Students Use These Powerful Tools to Master Trees For their A-Level Exams.

Other Revision Notes related to Trees you should explore