12. Binary Trees

Written by Kelvin Lau

In the previous chapter, you looked at a basic tree in which each node can have many children. A binary tree is a tree in which 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 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.

Note: This algorithm is based on an implementation by Károly Lőrentey in his book Optimizing Collections, available from https://www.objc.io/books/optimizing-collections/.

Add the following to the bottom of BinaryNode.swift:

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 + " ")
  }
}

diagram will recursively create a string representing the binary tree. To try it out, head back to the playground and write the following:

example(of: "tree diagram") {
  print(tree)
}

You should see the following console output:

---Example of tree diagram---
 ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
 └──0

You’ll use this diagram for other binary trees in this book.

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:

• If the current node has a left child, recursively visit this child first.
• Then visit the node itself.
• If the current node has a right child, recursively visit this child.

Here’s what an in-order traversal looks like for your example tree:

You may have noticed that this prints the example tree in ascending order. If the tree nodes are structured in a certain way, in-order traversal visits them in ascending order! You’ll learn more about binary search trees in the next chapter.

Open up BinaryNode.swift and add the following code to the bottom of the file:

extension BinaryNode {

  public func traverseInOrder(visit: (Element) -> Void) {
    leftChild?.traverseInOrder(visit: visit)
    visit(value)
    rightChild?.traverseInOrder(visit: visit)
  }
}

Following the rules laid out above, you first traverse to the left-most node before visiting the value. You then traverse to the right-most node. Head back to the playground page to test this out. Add the following at the bottom of the page:

example(of: "in-order traversal") {
  tree.traverseInOrder { print($0) }
}

You should see the following in the console:

---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:

Write the following just below your in-order traversal method:

public func traversePreOrder(visit: (Element) -> Void) {
  visit(value)
  leftChild?.traversePreOrder(visit: visit)
  rightChild?.traversePreOrder(visit: visit)
}

Test it out with the following code:

example(of: "pre-order traversal") {
  tree.traversePreOrder { print($0) }
}

You should see the following output in the console:

---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.

In other words, given any node, you’ll visit its children before visiting itself. An interesting consequence of this is that the root node is always visited last.

Back inside BinaryNode.swift, write the following below traversePreOrder:

public func traversePostOrder(visit: (Element) -> Void) {
  leftChild?.traversePostOrder(visit: visit)
  rightChild?.traversePostOrder(visit: visit)
  visit(value)
}

Navigate back to the playground page to try it out:

example(of: "post-order traversal") {
  tree.traversePostOrder { print($0) }
}

You should see the following in the console:

---Example of post-order traversal---
0
5
1
8
9
7

Each one of these traversal algorithms has both a time and space complexity of O(n). While this version of the binary tree isn’t too interesting, you saw that in-order traversal can be used to visit the nodes in ascending order. Binary trees can enforce this behavior by adhering to some rules during insertion. In the next chapter, you’ll look at a binary tree with stricter semantics: the binary search tree.

Key points

• The binary tree is the foundation to 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.