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

### 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)**.

### 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 **2**^{h} – 1

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