12 Binary Trees Written by Kelvin Lau

In the previous chapter, you looked at a basic tree where each node can have many children. A binary tree is a tree where each node has at most two children, often referred to as the left and right children:

Binary trees serve as the basis for many tree structures and algorithms. In this chapter, you’ll build a binary tree and learn about the three most important tree traversal algorithms.

Implementation

Open the starter project for this chapter. Create a new file and name it BinaryNode.swift. Add the following inside this file:

``````public class BinaryNode<Element> {

public var value: Element
public var leftChild: BinaryNode?
public var rightChild: BinaryNode?

public init(value: Element) {
self.value = value
}
}
``````

In the main playground page, add the following:

``````var tree: BinaryNode<Int> = {
let zero = BinaryNode(value: 0)
let one = BinaryNode(value: 1)
let five = BinaryNode(value: 5)
let seven = BinaryNode(value: 7)
let eight = BinaryNode(value: 8)
let nine = BinaryNode(value: 9)

seven.leftChild = one
one.leftChild = zero
one.rightChild = five
seven.rightChild = nine
nine.leftChild = eight

return seven
}()
``````

This code defines the following tree by executing the closure:

Building a diagram

Building a mental model of a data structure can be quite helpful in learning how it works. To that end, you’ll implement a reusable algorithm that helps visualize a binary tree in the console.

``````extension BinaryNode: CustomStringConvertible {

public var description: String {
diagram(for: self)
}

private func diagram(for node: BinaryNode?,
_ top: String = "",
_ root: String = "",
_ bottom: String = "") -> String {
guard let node = node else {
return root + "nil\n"
}
if node.leftChild == nil && node.rightChild == nil {
return root + "\(node.value)\n"
}
return diagram(for: node.rightChild,
top + " ", top + "┌──", top + "│ ")
+ root + "\(node.value)\n"
+ diagram(for: node.leftChild,
bottom + "│ ", bottom + "└──", bottom + " ")
}
}
``````
``````example(of: "tree diagram") {
print(tree)
}
``````
``````---Example of tree diagram---
┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
└──0
``````

Traversal algorithms

Previously, you looked at a level-order traversal of a tree. With a few tweaks, you can make this algorithm work for binary trees as well. However, instead of re-implementing level-order traversal, you’ll look at three traversal algorithms for binary trees: in-order, pre-order and post-order traversals.

In-order traversal

In-order traversal visits the nodes of a binary tree in the following order, starting from the root node:

``````extension BinaryNode {

public func traverseInOrder(visit: (Element) -> Void) {
leftChild?.traverseInOrder(visit: visit)
visit(value)
rightChild?.traverseInOrder(visit: visit)
}
}
``````
``````example(of: "in-order traversal") {
tree.traverseInOrder { print(\$0) }
}
``````
``````---Example of in-order traversal---
0
1
5
7
8
9
``````

Pre-order traversal

Pre-order traversal always visits the current node first, then recursively visits the left and right child:

``````public func traversePreOrder(visit: (Element) -> Void) {
visit(value)
leftChild?.traversePreOrder(visit: visit)
rightChild?.traversePreOrder(visit: visit)
}
``````
``````example(of: "pre-order traversal") {
tree.traversePreOrder { print(\$0) }
}
``````
``````---Example of pre-order traversal---
7
1
0
5
9
8
``````

Post-order traversal

Post-order traversal only visits the current node after the left and right child have been visited recursively.

``````public func traversePostOrder(visit: (Element) -> Void) {
leftChild?.traversePostOrder(visit: visit)
rightChild?.traversePostOrder(visit: visit)
visit(value)
}
``````
``````example(of: "post-order traversal") {
tree.traversePostOrder { print(\$0) }
}
``````
``````---Example of post-order traversal---
0
5
1
8
9
7
``````

Key points

• The binary tree is the foundation of some of the most important tree structures. The binary search tree and AVL tree are binary trees that impose restrictions on the insertion/deletion behaviors.
• In-order, pre-order and post-order traversals aren’t just important only for the binary tree; if you’re processing data in any tree, you’ll use these traversals regularly.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.