A binary tree is a tree data structure in which each node has at most two children. Each node of a binary tree consists of three items:
- Data item
- Address of the left child
- Address of the right child
Here is a visual representation of a Binary Tree:
Binary Tree Implementation in Swift:
Here’s how we can implement a binary tree in Swift:
Step 1: Define the Binary Tree Node
First, define the BinaryTreeNode class with a value, a left child, and a right child.
class BinaryTreeNode<T> {
var value: T
var leftChild: BinaryTreeNode?
var rightChild: BinaryTreeNode?
init(value: T) {
self.value = value
self.leftChild = nil
self.rightChild = nil
}
}
Step 2: Create and Manipulate the Tree
If we try to represent the above tree, we can implement this:
// Create the root node
let root = BinaryTreeNode(value: "root - A")
// Create child nodes
let leftChild = BinaryTreeNode(value: "leftChild - B")
let rightChild = BinaryTreeNode(value: "rightChild - C")
// Assign children to the root
root.leftChild = leftChild
root.rightChild = rightChild
// Add grandchildren
let leftGrandChild = BinaryTreeNode(value: "leftGrandChild - D")
let rightGrandChild = BinaryTreeNode(value: "leftGrandChild - E")
leftChild.leftChild = leftGrandChild
leftChild.rightChild = rightGrandChild
Step 3: Implement Binary Tree Traversals
We can implement several types of traversals like in-order, pre-order, and post-order, etc.
In-order traversal: In-order traversal visits the left child, the node itself, and then the right child.
func inOrderTraversal<T>(node: BinaryTreeNode<T>?) {
guard let node = node else { return }
inOrderTraversal(node: node.leftChild)
print(node.value)
inOrderTraversal(node: node.rightChild)
}
Here is the full code for Binary Tree implementation with In-Order Traversal:
class BinaryTreeNode<T> {
var value: T
var leftChild: BinaryTreeNode?
var rightChild: BinaryTreeNode?
init(value: T) {
self.value = value
self.leftChild = nil
self.rightChild = nil
}
}
func inOrderTraversal<T>(node: BinaryTreeNode<T>?) {
guard let node = node else { return }
inOrderTraversal(node: node.leftChild)
print(node.value)
inOrderTraversal(node: node.rightChild)
}
// Create the root node
let root = BinaryTreeNode(value: "root - A")
// Create child nodes
let leftChild = BinaryTreeNode(value: "leftChild - B")
let rightChild = BinaryTreeNode(value: "rightChild - C")
// Assign children to the root
root.leftChild = leftChild
root.rightChild = rightChild
// Add grandchildren
let leftGrandChild = BinaryTreeNode(value: "leftGrandChild - D")
let rightGrandChild = BinaryTreeNode(value: "leftGrandChild - E")
leftChild.leftChild = leftGrandChild
leftChild.rightChild = rightGrandChild
// Perform In-Order Traversal starting from the root
print("In-Order Traversal:")
inOrderTraversal(node: root)
The output will be:
In-Order Traversal:
leftGrandChild - D
leftChild - B
leftGrandChild - E
root - A
rightChild - C
Pre-Order Traversal
Pre-order traversal visits the node itself, then the left child, and then the right child. Here is the function for Pre-Order Traversal:
func preOrderTraversal<T>(node: BinaryTreeNode<T>?) {
guard let node = node else { return }
print(node.value)
preOrderTraversal(node: node.leftChild)
preOrderTraversal(node: node.rightChild)
}
Post-Order Traversal
Post-order traversal visits the left child, the right child, and then the node itself. Here is the function for Post-Order Traversal:
func postOrderTraversal<T>(node: BinaryTreeNode<T>?) {
guard let node = node else { return }
postOrderTraversal(node: node.leftChild)
postOrderTraversal(node: node.rightChild)
print(node.value)
}
Automatically insert items in the tree:
In the previous example, we have inserted nodes in the tree manually. We can automatically insert items in the tree. It will balance the Binary Tree automatically. Here is the full code:
import Foundation
class BinaryTreeNode<T> {
var value: T
var leftChild: BinaryTreeNode?
var rightChild: BinaryTreeNode?
init(value: T) {
self.value = value
self.leftChild = nil
self.rightChild = nil
}
}
class BinaryTree<T> {
var root: BinaryTreeNode<T>?
func insert(array: [T]) {
guard !array.isEmpty else { return }
self.root = BinaryTreeNode(value: array[0])
var queue: [BinaryTreeNode<T>] = [self.root!]
var index = 1
while index < array.count {
let currentNode = queue.removeFirst()
if index < array.count {
currentNode.leftChild = BinaryTreeNode(value: array[index])
queue.append(currentNode.leftChild!)
index += 1
}
if index < array.count {
currentNode.rightChild = BinaryTreeNode(value: array[index])
queue.append(currentNode.rightChild!)
index += 1
}
}
}
// In-Order Traversal
func inOrderTraversal(node: BinaryTreeNode<T>?) {
guard let node = node else { return }
inOrderTraversal(node: node.leftChild)
print(node.value)
inOrderTraversal(node: node.rightChild)
}
}
let elements = ["A", "B", "C", "D", "E", "F"]
let tree = BinaryTree<String>()
tree.insert(array: elements)
print("In-Order Traversal:")
tree.inOrderTraversal(node: tree.root)
Explanation of insert Method:
func insert(array: [T]) {
guard !array.isEmpty else { return }
self.root = BinaryTreeNode(value: array[0])
var queue: [BinaryTreeNode<T>] = [self.root!]
var index = 1
while index < array.count {
let currentNode = queue.removeFirst()
if index < array.count {
currentNode.leftChild = BinaryTreeNode(value: array[index])
queue.append(currentNode.leftChild!)
index += 1
}
if index < array.count {
currentNode.rightChild = BinaryTreeNode(value: array[index])
queue.append(currentNode.rightChild!)
index += 1
}
}
}
- Parameter:
array– an array of elements to be inserted into the tree in level order. - Guard Clause: Checks if the array is empty; if so, it returns immediately.
- Initialize Root: Sets the root node with the first element of the array.
- Queue: Uses a queue to manage nodes while inserting children level by level.
- Index: Tracks the current position in the array.
- While Loop: Continues until all elements are inserted:
- Removes the first node from the queue.
- Inserts the left child if the current index is within bounds.
- Inserts the right child if the current index is within bounds.
- Appends newly created child nodes to the queue.
The resulting Tree will be like this:
We have implemented In-Order Traversal. The output will be:
In-Order Traversal:
D
B
E
A
F
C