What is a Binary Tree?

The literal meaning of the word binary is dual or double. In the computational world, binary is often described as a pair of zero and one. Tree is a data structure that graphically represents a tangible tree but only upside down. Combining these two words, we get a hierarchical data structure called the binary tree. A binary tree is such a tree where every element will at most have two children. It is therefore easy to segregate the right child from the left child.

The root of a binary tree is the element that sits right at the top of the data structure and hierarchy. All elements to the left of the root are called the left branch and all elements to the right of the tree are called the right branch. Each element in a tree can be treated as a node. The node essentially has three elements.

• Data
• Pointer to the left child
• Pointer to the right child.

In case a node does not have a child, the pointer points to null.

Implementation of Trees in JAVA

The following class implements a node of a tree that has two children. The key is the value of the node. For this example, we have not allocated nodes to the root.

class Node
{
int key;
Node left, right;
public Node (int item)
{
key = item;
left = right = null;
}
}

//The following program will device a simple tree that will have the structure as follows:

class Node
{
int key;
Node left,right;
public Node (int item)
{
key = item;
left = right = null;
}
}
class Binary Tree
{
//The root of the tree i.e. 1 in this case
Node root;
//Constructor
BinaryTree (int key)
{
root = new Node (key);
}
BinaryTree()
{
root = null;
}
public static void main (String args [])
{
BinaryTree tree = new BinaryTree();
//making the root
tree.rott = new Node (1);
//left child
tree.root.left = new Node(2);
//right child
tree.root.right = new Node(3);
//This completes the first layer of the tree
//As only the left branch has a value let us add the leaf
tree.root.left.left = new Node (4);
}
}

Properties of Binary Tree

• A binary tree can have at maximum 2ⁱ nodes at level i. The root of a tree is considered to be level 0. Therefore 2^0 = 1 i.e. at the root level the tree can only have one node. At level one: 2^1 = 2 nodes and so on.
• A binary tree of height ‘h’ will have a maximum of 2^{h – 1} number of nodes. If a tree has a height of 4, it can have a maximum of 2^(4-1) = 8 nodes.
• The formula to derive the minimum height or levels of a binary tree of N nodes is as follows: Log₂ (N + 1).
• If a binary tree has L number of leaves (leaves have no children), then the minimum number of layers that the tree will have is given by the formula: Log₂L + 1.
• If in a binary tree, every node has either 0 or 2 children, then the total number of leaves (nodes with 0 children) will always be one more than nodes that have two children.

Traversal

Let us take the following tree as presented before to talk about traversals.

There are three ways to traverse trees. They are as follows:

• Inorder Traversal: Here we start from the left leaf of the left branch, visit the parent, traverse the right child of the parent, go to the root, and traverse the right branch.
  In this example: 4 2 5 1 3
• PreOrder Traversal: This traversal starts from the root of the tree. It then travels to all the left children of the left branch until it reaches a leaf. Then it goes back to the parent and traverses the right child. Once the left branch is done, it follows the same process to traverse the right branch.
  In this example: 1 2 4 5 3
• PostOrder Traversal: Post Order starts from the left leaf of the left branch and traverses all the other child before going to the parent. This means that the root is always traversed at the end.
  In this example: 4 5 2 3 1