Trees

Overview

A tree is a hierarchical data structure made up of nodes connected by edges. Unlike linear structures like arrays, stacks, or queues, trees represent relationships in a branching format, which makes them ideal for representing hierarchical data such as file systems, organizational charts, and syntactic structures.

In Swift, trees can be implemented using classes or structs, often using recursion to navigate their nested structure.

Tree Terminology

• Node: A basic unit containing data and child references.

• Root: The topmost node in a tree.

• Leaf: A node with no children.

• Parent/Child: Nodes connected directly in a one-level relationship.

• Subtree: A smaller tree that is part of a larger one.

• Depth: The distance from the root to a node.

• Height: The longest path from a node to a leaf.

Binary Tree

A binary tree is a type of tree where each node has at most two children: left and right.

Binary Tree Node

class TreeNode<T> {
	var value: T
	var left: TreeNode?
	var right: TreeNode?

	init(value: T) {
		self.value = value
	}
}

Tree Traversal

Tree traversal is the process of visiting all nodes in a specific order.

In-Order Traversal (Left → Root → Right)

func inOrder<T>(_ node: TreeNode<T>?) {
	guard let node = node else { return }
	inOrder(node.left)
	print(node.value)
	inOrder(node.right)
}

Pre-Order Traversal (Root → Left → Right)

func preOrder<T>(_ node: TreeNode<T>?) {
	guard let node = node else { return }
	print(node.value)
	preOrder(node.left)
	preOrder(node.right)
}

Post-Order Traversal (Left → Right → Root)

func postOrder<T>(_ node: TreeNode<T>?) {
	guard let node = node else { return }
	postOrder(node.left)
	postOrder(node.right)
	print(node.value)
}

Level-Order Traversal (Breadth-First)

func levelOrder<T>(_ root: TreeNode<T>?) {
	guard let root = root else { return }
	var queue: [TreeNode<T>] = [root]

	while !queue.isEmpty {
		let node = queue.removeFirst()
		print(node.value)
		if let left = node.left { queue.append(left) }
		if let right = node.right { queue.append(right) }
	}
}

Binary Search Tree (BST)

A binary search tree is a binary tree where for each node:

• The left child contains values less than the node.

• The right child contains values greater than the node.

BST Insertion

func insert<T: Comparable>(_ node: TreeNode<T>?, _ value: T) -> TreeNode<T> {
	guard let node = node else {
		return TreeNode(value: value)
	}

	if value < node.value {
		node.left = insert(node.left, value)
	} else {
		node.right = insert(node.right, value)
	}

	return node
}

BST Search

func search<T: Comparable>(_ node: TreeNode<T>?, _ value: T) -> Bool {
	guard let node = node else { return false }

	if value == node.value {
		return true
	} else if value < node.value {
		return search(node.left, value)
	} else {
		return search(node.right, value)
	}
}

Performance Characteristics

Use Cases

• Binary Search Trees (efficient searching/sorting)

• Expression Trees (used in parsers)

• DOM trees in HTML/XML

• File system hierarchies

• Game AI decision trees

• Syntax trees in compilers

Advanced Tree Types

• AVL Trees: Self-balancing BSTs for guaranteed O(log n) operations.

• Red-Black Trees: Used in Swift’s Set and Dictionary.

• Trie: Prefix tree for string-based searches (e.g., autocomplete).

• N-ary Trees: Nodes can have any number of children.

Best Practices

• Use classes when reference semantics are important.

• Avoid deep recursion in large trees (consider iterative traversal).

• When searching frequently, balance your tree structure.

• Use visualizations to debug and understand tree structures.

Conclusion

Trees are powerful and versatile structures in computer science. Swift gives you the flexibility to build and traverse trees using simple, expressive syntax. Mastery of trees—especially binary trees and their variants—opens the door to solving many complex problems in an efficient manner.

In the next chapter, we’ll explore Heaps and Priority Queues, which build on tree concepts to enable efficient minimum/maximum element retrieval.