Tree Data Structures in Swift

by

A tree is a nonlinear data structure that consists of nodes. Nodes are connected by edges. Each node of a Tree has a value and zero or more child nodes. Trees are useful for representing hierarchical data. Here is a visual representation of a Tree:

Tree Terminologies

Understanding Tree terminology is essential for grasping tree-based data structures and algorithms. Here’s a comprehensive overview of key terms related to Trees:

  • Node: A fundamental part of a tree that contains a value or data and references to other nodes (children).
  • Edge: A connection between two nodes.
  • Root: The topmost node in a tree, where the traversal begins. It has no parent.
  • Child: A node that has a parent. Children are nodes connected directly to another node moving away from the root.
  • Parent: A node that has one or more children.
  • Sibling: Nodes that share the same parent.
  • Leaf (External Node): A node with no children. It is the end point of a path.
  • Internal Node: A node with at least one child.
  • Degree of a Node: The number of children a node has.
  • Degree of a Tree: The maximum degree of any node in the tree.
  • Path: A sequence of nodes and edges connecting a node with a descendant.
  • Ancestor: Any node along the path from the node to the root, including the node itself.
  • Descendant: Any node along the path from a node to a leaf, including the node itself.
  • Subtree: A tree consisting of a node and all its descendants.
  • Level (Depth): The number of edges from the root to the node. The root node is at level 0.
  • Height of a Node: The number of edges on the longest path from the node to a leaf. The height of a tree is the height of the root node.
  • Height of a Tree: The number of edges on the longest path from the root to a leaf.
  • Depth of a Node: The number of edges from the root to the node.

Tree Traversal Methods

Tree traversal is the process of visiting all the nodes in a tree data structure in a specific order. Traversing a tree means systematically visiting each node exactly once in a manner that ensures every node is processed. Different traversal methods yield different orders of node visits, which are useful for various tree operations and algorithms.

Here are the main types of tree traversal methods:

1. Depth-First Search (DFS)

DFS explores as far down a branch as possible before backtracking. It can be implemented in three different ways:

  1. In-Order Traversal
  2. Pre-Order Traversal
  3. Post-Order Traversal

2. Breadth-First Search (BFS) or Level-Order Traversal

BFS visits nodes level by level from left to right. It uses a queue to keep track of nodes at the current level before moving on to the next level.

Tree Implementation in Swift:

Here’s how we can implement a simple tree in Swift:

Step 1: Define the Tree Node

First, we define a TreeNode class that will hold the value and the children.

class TreeNode<T> {
    var value: T
    var children: [TreeNode]

    init(value: T) {
        self.value = value
        self.children = []
    }

    func addChild(_ node: TreeNode) {
        children.append(node)
    }
}

Step 2: Create and Manipulate the Tree

Now we can create a tree and add nodes to it.

// Create the root node
let root = TreeNode(value: "root")

// Create child nodes
let child1 = TreeNode(value: "child1")
let child2 = TreeNode(value: "child2")

// Add children to the root
root.addChild(child1)
root.addChild(child2)

// Add grandchildren
let grandChild1 = TreeNode(value: "grandChild1")
child1.addChild(grandChild1)

// Add more nodes as needed

Step 3: Tree Traversal

To traverse the tree, you can implement various traversal methods such as depth-first search (DFS) or breadth-first search (BFS).

Depth-First Search (DFS)

Here’s how you might implement DFS to print all the nodes in the tree:

func dfs(node: TreeNode<String>) {
    print(node.value)
    for child in node.children {
        dfs(node: child)
    }
}

// Perform DFS starting from the root
dfs(node: root)

Breadth-First Search (BFS)

Here’s how you might implement BFS using a queue:

func bfs(node: TreeNode<String>) {
    var queue: [TreeNode] = [node]
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        print(current.value)
        queue.append(contentsOf: current.children)
    }
}

// Perform BFS starting from the root
bfs(node: root)

Example Usage

Here is a full example putting everything together:

import Foundation

class TreeNode<T> {
    var value: T
    var children: [TreeNode]

    init(value: T) {
        self.value = value
        self.children = []
    }

    func addChild(_ node: TreeNode) {
        children.append(node)
    }
}

func dfs(node: TreeNode<String>) {
    print(node.value)
    for child in node.children {
        dfs(node: child)
    }
}

func bfs(node: TreeNode<String>) {
    var queue: [TreeNode] = [node]
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        print(current.value)
        queue.append(contentsOf: current.children)
    }
}

// Create the root node
let root = TreeNode(value: "root")

// Create child nodes
let child1 = TreeNode(value: "child1")
let child2 = TreeNode(value: "child2")

// Add children to the root
root.addChild(child1)
root.addChild(child2)

// Add grandchildren
let grandChild1 = TreeNode(value: "grandChild1")
child1.addChild(grandChild1)

// Perform DFS starting from the root
print("DFS Traversal:")
dfs(node: root)

// Perform BFS starting from the root
print("\nBFS Traversal:")
bfs(node: root)

Leave a Reply