Trees

Overview

A tree is a hierarchical data structure consisting of nodes. Trees are used to represent relationships, such as family trees, organisational charts, and file systems. In Computer Science, trees are widely used for efficient data searching, sorting, and hierarchical data representation.

Structure of a Tree

• Node: The fundamental unit of a tree, containing data and references to child nodes.
• Root: The topmost node in the tree.
• Edge: A connection between a parent and a child node.
• Parent: A node that has one or more child nodes.
• Child: A node that has a parent node.
• Leaf: A node with no children.
• Subtree: A smaller tree within a larger tree, consisting of a node and its descendants.

Types of Trees

• Binary Tree: Each node has at most two children, typically referred to as the left and right child.
• Binary Search Tree (BST): A binary tree where the left child contains values less than the parent, and the right child contains values greater than the parent.
• Multi-branch Tree: A tree where nodes can have more than two children.

Use Cases for Trees

• Binary Search Trees: Efficient for searching, insertion, and deletion (O(log n) time complexity in a balanced tree).
• File Systems: Organising files and directories.
• Heaps: Priority queues.
• Trie: Searching words in a dictionary.

Implementing a Tree

Dynamic Implementation Using Linked Nodes

A tree can be implemented dynamically using linked nodes.

CLASS Node
    DATA value
    POINTER left
    POINTER right

CLASS BinaryTree
    POINTER root

    METHOD Add(value)
        IF root IS NULL
            root ← NEW Node(value)
        ELSE
            CALL AddRecursive(root, value)

    METHOD AddRecursive(current, value)
        IF value < current.value
            IF current.left IS NULL
                current.left ← NEW Node(value)
            ELSE
                CALL AddRecursive(current.left, value)
        ELSE
            IF current.right IS NULL
                current.right ← NEW Node(value)
            ELSE
                CALL AddRecursive(current.right, value)

Static Implementation Using an Array

A binary tree can also be implemented using an array where:

• The root is at index 0.
• The left child of a node at index i is at 2*i + 1.
• The right child is at 2*i + 2.

Tree Traversals

Depth-First Traversal (Post-Order)

In post-order traversal, the nodes are visited in this order:

Left Subtree → Right Subtree → Root

Given Tree:
      A
     / \\
    B   C
   / \\
  D   E

Post-Order: D → E → B → C → A

METHOD PostOrder(node)
    IF node IS NOT NULL
        CALL PostOrder(node.left)
        CALL PostOrder(node.right)
        OUTPUT node.value

Breadth-First Traversal

Also known as Level-Order Traversal, nodes are visited level by level, from left to right.

Given Tree:
      A
     / \\
    B   C
   / \\
  D   E

Breadth-First: A → B → C → D → E

METHOD BreadthFirst(root)
    INITIALISE queue
    ENQUEUE root

    WHILE queue IS NOT EMPTY
        current ← DEQUEUE queue
        OUTPUT current.value
        IF current.left IS NOT NULL
            ENQUEUE current.left
        IF current.right IS NOT NULL
            ENQUEUE current.right

Adding and Removing Nodes in a Binary Search Tree

Adding a Node:

1. Start at the root. 2. Traverse left if the value is smaller or right if it is larger. 3. Insert the node at the appropriate leaf position.

Removing a Node:

1. If the node has no children: Remove it directly. 2. If the node has one child: Replace it with its child. 3. If the node has two children: Replace it with the in-order successor (smallest value in the right subtree).

Note Summary