Home iOS & Swift Books Data Structures & Algorithms in Swift

12
Binary Trees Written by Kelvin Lau

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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.

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:

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

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

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.