Data Structures & Algorithms in Swift: Part 3 — Binary Tree
What is a Tree?
Tree is a hierarchical data structure unlike stack and queue which are linear in nature. Trees are used to represent and hold data which have hierarchy in their nature, for example we can represent a family tree via Tree data structure. They can also be used to perform efficient searches on a huge dataset. You can think of it as a real-world tree which is upside down, root at the top and branches growing downwards. Let’s learn about different terminologies that are used to represent different parts of a tree.
Terminology related to Tree
NODE
Tree is a combination of nodes. Each entity is represented by a single node in a tree.
In figure A 1 , 2 and 3 are three different nodes of a tree.
ROOT/ROOT NODE
Root node is the topmost node in a tree. This is node where tree start growing downwards. In figure A Node -> 1 is the root node.
CHILD NODE
Each node in a tree can have different child nodes. It is not compulsory that every node should have a child. In figure A Node -> 2 and Node -> 3 are the children of Node -> 1
PARENT NODE
Every child node has a parent node. Every child node can have exactly one parent node whereas a parent node can have any number of child nodes starting from 0. In figure A Node -> 1 is the parent of Node -> 2 and Node -> 3
LEAF NODE
A node which has no children is called as a leaf node. In figure A Node -2 and Node -> 3 both are leaf nodes as they don’t have child nodes.
What is a Binary Tree?
Binary tree is a special case of Tree in which every node can have 0, 1 or 2 child nodes. All the remaining things are same but the only difference is how many child a parent can hold.
Let’s understand a binary tree by using figure B.
Since a binary tree can have at most 2 child nodes we use a different term to represent a child node. We use Left child and Right child to represent children in a binary tree. To summarise a node in a binary tree can have 0 child nodes, 1 left child, 1 right child or both left and right child nodes.
Node -> 2 is a left child of Node -> 1
Node -> 3 is a right child of Node -> 1
Node -> 4 is a left child of Node -> 2
Node -> 5 is a right child of Node -> 2
Node -> 6 is a right child of Node -> 3
Node -> 3 does not have a left child.
Node -> 4 Node -> 5 and Node -> 6 have 0 child nodes and hence are called leaf nodes.
Implementation of a Binary Tree
Open Xcode & create a new playground BinaryTree
As we know that binary tree is just a combination of different nodes so we will create a separate class to hold data related to a single node.
Our class BinaryNode has three different elements in it.
Value-> This will hold the value of the node. For example we can create an integer binary tree and this can hold any integer value.LeftChild-> Left child is a type of Binary Node and it is an optional value because a node can or cannot have a child node.RightChild-> Right child is also a type of Binary Node and it is made optional for a similar reason.
We have an initialiser which only takes value as a parameter because the rest of the things are optional.
Let’s start creating this binary tree (Figure C) using the BinaryNode that we have just created.
Step 1 -> We are creating a root node with an integer value of 7.
Step 2 -> In this step we are creating all the remaining nodes of the tree.
Step 3 -> We are adding Node -> 1 and Node -> 2 as the left and right child of Node -> 7
Step 4 -> We are adding Node -> 3 and Node -> 8 as the left and right child of Node -> 1
Step 5 -> We are adding Node -> 9 and Node -> 6 as the left and right child of Node -> 2
Step 6 -> We are simply returning the root node which will be the starting node of our binaryTree
Traverse a Binary Tree
There are 3 different ways in which we can traverse a binary tree. We will understand all three of them and use it on the binary tree that we have just created.
Inorder Traversal
The basic rule of inorder traversal is Left child -> Parent -> Right childThis basically means that for every node you visit first print the left child then the node itself and in the end the right child. For the above figure, inorder traversal will be Inorder -> 3 1 8 7 9 2 6
We’ll start from the root node and we will continue to traverse until we find the leftmost child node (in our case it is Node -> 3 ). After that, we will move on the parent node which is Node -> 1 and then to the right child which is Node -> 8
We will continue the same process of left -> parent -> right until all the nodes have been visited. Since we have visited the left child of Node -> 7 we will now visit Node -> 7 and then we will find the leftmost child in the right subtree. In this case, Node -> 9 is the leftmost child and then Node -> 2 and Node -> 6
We can create an extension on BinaryNode which will traverse the binary tree using Inorder traversal
First, we call leftChild?.traverseInorder() which will find the leftmost child recursively and when the left child is nil it will print the value and then continue to the parent node and then to the right child.
Preorder Traversal
The basic rule of preorder traversal is Parent -> Left child -> Right child
This basically means that for every node you visit first print its value and then its left child and then right child. For the same figure preorder traversal will be Preorder -> 7 1 3 8 2 9 6
We will add another function to the BinaryNode extension which will be used to traverse the binary tree in preorder manner.
First, we print the value of the parent node and then we visit left child recursively until the value is nil and then we visit the right child recursively until the value is nil and we print out its value.
Postorder Traversal
The basic rule of postorder traversal is Left child -> Right child -> Parent
This basically means that for every node we first visit and print the left child followed by right child and in the end the node itself. For the same tree, the postorder traversal will be Postorder -> 3 8 1 9 6 2 7
We will add another function to the BinaryNode extension which will be used to traverse the binary tree in a postorder manner.
First, we recursively call the left child and print its value when the left child is nil followed by calling left recursively and printing its value when right child is nil and in the end we will print the value of the parent node.
Wrapping Up
Thanks for reading this. Hope you gained some knowledge with this post. All three different traversals can be confusing in the beginning. I suggest you create different binary trees and try to traverse the tree with different traversal algorithms. You can always cross-check your answer by running the traversal methods that we have created.
Feel free to ask any questions or discuss anything in the comments section.
You can download the full source code from Github.
