Tree (Data Structure)

A tree is a type of dynamic data structure that consists of nodes linked to a single parent node (except for the root node) and which can be linked to multiple children nodes. Each node contains "three" parameters, the data, some data structure storing the address of it's children nodes, and a address to it's parent node.

The tree data structure can be thought of as an implementation of a finite tree. Tree's can alternatively be thought of as a subset of graphs which have no cycles. Because tree's have no cycles, recursion is a useful technique for traversing them.

Terminology

Tree's are a type of graph and thus the same terminology also applies, each connection between a parent and a child is an edge.

Root - The first node of the tree (has no parent node).
Leaf - The last nodes of the tree (has no children nodes).
Breadth - The number of leaves in the tree.
Width - The number of nodes in a given level.
Height - The length of the longest path from the root to a leaf.
Depth / Level - The length of the path from the root to the given descendant
Descendant - A node that is reachable through repeated proceeding from parent to child.
Ancestor - A node that is reachable through repeated proceeding from child to parent.
Subtree - Any node in the tree along with all of its descendants.

Traversal

Tree traversal refers to the process by which you access nodes in the tree, each defines a specific order, and each no is only visited once.

Depth-First Tree Traversal

Depth first traversal is a method of traversing trees which explores as far along a given branch as possible before exploring the next branch.

Types

There are 2 general types of depth-first traversal, each of which determines the order in which the root is visited compared to the subtree are visited.

Preorder Traversal

In preorder traversal, the node is processed before its subtrees. This traversal is useful for creating a copy of the tree or generating a prefix notation of an expression tree.

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


def preorder_traverse(root, visit):
    if root is None:
        return

    visit(root.value)

    for child in root.children:
        preorder_traverse(child, visit)

Postorder Traversal

In postorder traversal, the node is processed after its subtrees. This traversal is useful for tasks such as deleting the tree or generating a postfix notation of an expression tree. It works for general trees as well.

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


def postorder_traverse(root, visit):
    if root is None:
        return

    for child in root.children:
        postorder_traverse(child, visit)

    visit(root.value)

Breadth-First Tree Traversal

Breadth first traversal is a method of traversing trees which explores all the nodes at a give level before descending to the next.

The standard implementation uses a queue where elements are pulled from the front of the queue to be processed and then their children are pushed to the end of the queue.

from collections import deque

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


def breadth_first_traversal(root, visit):
    if root is None:
        return

	queue = deque([root])

	while queue:
		current_node = queue.popleft()
		visit(current_node.value)

		if current_node.left:
			queue.append(current_node.left)
		if current_node.right:
			queue.append(current_node.right)