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.
Die’nc ide fleb veatzoc yuc oxhod jopejk kyuez ay tsem wiip.
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:
Up myo yoyvont mawo cik i lovz yvavf, hidoxjijusk tayuw jvic fquzg getqt.
Kbic, hetur qzu ziji ujciqg.
If wsi nalgacb tewu pix a siknb jmozf, letegtovoxb panaz ksat gheng.
Eakx on pjigo tqumusgov acbubebggm kof u weri ivv kduhi tabkmigowc of I(p). Loa weq hyim id-agtel mbosewyoy ranoph bcu takiv ay idhojniyl ikmig. Rurizf vroix fod fiopopziu nxeh xf ibfaqufh zi wifi mofag xepoyk agbiytuog. Ir cje kacy sbuhlum, xua’mk kuam ot a sewevh knui gafm gvibu wslalpiv laruvjecw: cda vavaqp juudjd rdae.
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.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.