Home iOS & Swift Books Data Structures & Algorithms in Swift

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:



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.

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") {
---Example of tree diagram---
│ └──8
│ ┌──5

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:

0, 1, 5, 7, 8, 9
1, 3, 8, 1, 5, 8

extension BinaryNode {

  public func traverseInOrder(visit: (Element) -> Void) {
    leftChild?.traverseInOrder(visit: visit)
    rightChild?.traverseInOrder(visit: visit)
example(of: "in-order traversal") {
  tree.traverseInOrder { print($0) }
---Example of in-order traversal---

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) {
  leftChild?.traversePreOrder(visit: visit)
  rightChild?.traversePreOrder(visit: visit)
example(of: "pre-order traversal") {
  tree.traversePreOrder { print($0) }
---Example of pre-order traversal---

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)
example(of: "post-order traversal") {
  tree.traversePostOrder { print($0) }
---Example of post-order traversal---

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.



© 2021 Razeware LLC


Unlock Now
