Reading Time: 6 minutes
Definition
Binary tree is a non-linear data structure that is composed of two nodes at most. This is how the name “Binary” is formed. However, it is not necessary for the Child Nodes that they have to have two nodes, in fact they can have even zero, we will observe such types in the following chapters.
Furthermore, there is also a Binary Tree implementation called “Binary Search Tree(a.k.a ordered binary tree)” that preserves data in a sorted fashion. From this point on, we will be talking and focusing on Binary Search Tree. Let’s apprehend the characteristics of Binary Search Tree:
- Given key is compared to the root key, the lower placed on the left and the greater placed on the right,
- There are two ways of traversals; breadth first and depth first (will be detailed in a sub chapter) compared to one-dimensional arrays and linked lists,
- Average cases of Positional Access, Search, Insertion and Deletion operations are far faster in tree that is denoted as O(log n) in the Big O time complexity.
Additionally, during my research, I have found a very useful resource that exposes a visualized Binary Search Tree and its operations; https://www.cs.usfca.edu/~galles/visualization/BST.html
Let’s look into the source code how we can create a Binary Tree.
Node.java
public class Node {
Node leftNode;
Node rightNode;
int key;
Node(int key) {
this.key = key;
}
}
BinaryTree.java
public class BinaryTree {
private Node rootNode;
private final static int DATA_NOT_AVAILABLE = -1;
//The rest of the code can be obtained on GitHub
}
Glossary and Properties
Before diving into Binary Search Tree, we will need to have a ubiquitous language to apprehend all the terms used in this data structure.
Root: The only top most element that has no other nodes above it,
Node: Every member in the tree is known as Node including the root as well,
Parent Node: The node that has two children,
Child Node: A node that is associated with a parent node
Leaf: A leaf is a node that DOES NOT have any children,
Path/Edge: The lines that connect all available nodes,
Sub tree: It is a triangle shape in a tree. Essentially a parent with its two child nodes,
Height: The height of a tree is the number of the edges from the Root node to its deepest leaf.
Some Binary Tree Height Samples as follow:
Time and Space Complexities of Binary Tree
Image courtesy: www.bigocheatsheet.com
Types of Binary Trees
Full Binary Tree
Full Binary Tree is a tree type that consists of a rule that indicates that leaves can have zero or nodes have two children.
L + I + 1
L: Number of leaf nodes,
I: Number of internal nodes
Complete Binary Tree
Complete Tree is a type of a Binary Tree in which;
- Every level must be completely filled,
- All leaf elements must lean towards left direction,
- Exceptionally the last leaf might have a right child node
Furthermore, Complete Binary Tree is also a Heap
Perfect Binary Tree
Perfect Binary Tree consists of Full and Complete Binary Trees with two conditions of :
- all nodes have two children,
- all leaves are on the same level.
In addition, the height of tree is 2h – 1
Balanced Binary Tree
A Balanced Tree is composed of a balance between the left and the right nodes, but at most one side differs only by one, otherwise it will be considered as an Unbalanced Tree. The operations in a balanced tree are performed in O(log n) notation where n is the node number.
In Addition, Balanced Tree Type has other implementations such as AVL, Red-Black, Weight and Height Balanced Trees etc. It is a good practice to apprehend the definition of the balanced tree.
Unbalanced Binary Tree
Ordered data sets make up the unbalanced tree. In this type, most of the nodes are located on one side of the tree. In Unbalanced Trees, we cannot favor of fast operations denoted as O(log n), whereas it is actually O(n).
Tree Traversal
Tree Traversal is the acronym that is known as Tree Search is a type of an action that leads to visiting every single node in the tree and performing selection, insertion, updating and deletion. While going/traversing through there are number of ways to do so namely; Breadth First and Depth First traversals.
Breadth First Traversal
Breadth First Traversal traverses the tree in a level fashion. It internally utilizes a Queue Data Structure, to visit nodes in layers as you can see the illustration. The algorithm of Breadth First Traversal goes;
public void breadthFirstTraversal() {
if (rootNode == null)
return;
System.out.printf("***Breadth First Traversal***\n");
Queue<Node> queue = new ArrayDeque<>();
queue.add(rootNode);
while (!queue.isEmpty()) {
rootNode = queue.remove();
System.out.println(rootNode.key);
if (rootNode.leftNode != null)
queue.add(rootNode.leftNode);
if (rootNode.rightNode != null)
queue.add(rootNode.rightNode);
}
}
Console Output:
***Breadth First Traversal***
60
55
67
50
57
61
77
45
53
Depth First Traversal
Deep First travel is slightly different and more complicated compared to the Breadth first traversal. Basically, Depth first traversal, the actual focus is not the levels and layers but the Depth itself. Depth first algorithms will visit each node.
In Order Traversal
In Order Traversal has the following sequence:
- Left Node,
- Root Node,
- Right Node
Having said that when the traversal begins from the deepest left node. As the second item goes to the root, it is not the top root but the parent root. Then it follows the right node. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “77” the highest right node in the tree. Observe the code for traversal:
private void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.leftNode);
System.out.println(node.key);
inOrderTraversal(node.rightNode);
}
}
Console Output:
***In Order Traversal***
45
50
53
55
57
60
61
67
77
Pre Order Traversal
Pre Order Traversal has the following sequence:
- Root Node,
- Left Node,
- Right Node
Having said that when the traversal begins from the root node. As the second item goes to the next left root. Then here the algorithm starts to visit the left and accordingly the right node. As you see the above illustration, the algorithm starts in “60” the root node and ends in “77” the highest right node in the tree. Observe the code for traversal:
private void preOrderTraversal(Node node) {
if (node != null) {
System.out.println(node.key);
preOrderTraversal(node.leftNode);
preOrderTraversal(node.rightNode);
}
}
Console Output:
***Pre Order Traversal***
60
55
50
45
53
57
67
61
77
Post Order Traversal
Post Order Traversal has the following sequence:
- Left Node,
- Right Node,
- Root Node
Having said that when the traversal begins from the deepest left node. As the second item goes to the next right node. Last of all it visits the root node of the children. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “60” the root node. Observe the code for traversal:
private void postOrderTraversal(Node node) {
if (node != null) {
postOrderTraversal(node.leftNode);
postOrderTraversal(node.rightNode);
System.out.println(node.key);
}
}
Console Output:
***Post Order Traversal***
45
53
50
57
55
61
77
67
60
Code
The full source code of the Binary Tree and the test cases can be obtained from my public GitHub repository. There will be more utility methods and test cases covering the chapter.
https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures
