Binary Tree

**What is a Binary Tree?**

A binary tree is a tree data structure in which each node has at most two children (referred to as the left child and the right child). In a binary tree, the degree of each node can be at most two.

A single node in binary tree can be represented by a node itself and having left and right children as null. When there are two ore more, it starts becoming a tree like structure. Nodes other than root, are added either as a right child or as a left child of another node including root node.

**Time Complexity:**

- Insert Erase – O(h) where h = height
- Lookup / Indexing – O(h)
- Find – O(h)

In a worst case scenario, N = h, in a best case scenario, h = log(N).

Here is a simple representation of a binary tree in Java.

/**
* Binary Tree Node representation.
* - Node has a value, a left node and a right node.
* - Single node, when created, has left and right node as null.
*/
@SuppressWarnings("rawtypes")
public class BinaryTreeNode {
Comparable value;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(Comparable value) {
this.value = value;
this.left = null;
this.right = null;
}
}

**Tree Traversal:**

There are three popular binary tree traversal algorithms:

- Pre-Order Traversal
*Visit the root node*
*Traverse left subtree*
*Traverse right subtree*

- In-order Traversal
*Traverse left subtree*
*Visit the root node*
*Traverse right subtree*

- Post-order Traversal
*Traverse left subtree*
*Traverse right subtree*
*Visit the node*

**Java Implementation of Binary Tree and the three tree traversals:**

package com.icodejava.blog;
/**
* @author Kushal Paudyal
* www.icodejava.com
* Created On - Mar 3, 2014
* Last Modified On - Mar 3, 2014
*/
public class BinaryTreeTraversal {
public static void main(String args[]) {
BinaryTreeNode root = createBinaryTree();
System.out.println("IN ORDER TREE TRAVERSAL");
// In Order Tree Traversal - LEFT - ROOT - RIGHT.
traverseInOrder(root);
System.out.println("\n\nPRE ORDER TREE TRAVERSAL");
// Pre-Order Tree Traversal - ROOT - LEFT - RIGHT.
traversePreOrder(root);
System.out.println("\n\nPOST ORDER TREE TRAVERSAL");
// Post Order Tree Traversal - LEFT - RIGHT - ROOT.
traversePostOrder(root);
}
private static BinaryTreeNode createBinaryTree() {
// Creating a tree with following data. Root node being 15.
// 15,5,3,12,13,10,6,7,16,20,18,23.
BinaryTreeNode root = new BinaryTreeNode(15);
addNode(root, 5);
addNode(root, 3);
addNode(root, 12);
addNode(root, 13);
addNode(root, 10);
addNode(root, 6);
addNode(root, 7);
addNode(root, 16);
addNode(root, 20);
addNode(root, 18);
addNode(root, 23);
return root;
}
@SuppressWarnings({ "unchecked", "rawtypes" })
public static BinaryTreeNode addNode(BinaryTreeNode root, Comparable value) {
//if root is null
if(root == null) {
return new BinaryTreeNode(value);
}
//if the value is smaller than a node,
if(value.compareTo(root.value) < 0) {
root.left = addNode(root.left, value);
} else {
root.right = addNode(root.right, value);
}
return root;
}
/**
* IN-ORDER Traversal - Recursively Traverses LEFT-ROOT-RIGHT
* In order traversal results sorted order traverse.
*/
public static void traverseInOrder(BinaryTreeNode theRootNode) {
if (theRootNode != null) {
// left
traverseInOrder(theRootNode.left);
// root
System.out.print(theRootNode.value + ",");
// right
traverseInOrder(theRootNode.right);
}
}
/**
* PRE-ORDER Traversal - Recursively Traverses ROOT-LEFT-RIGHT
*/
public static void traversePreOrder(BinaryTreeNode theRootNode) {
if (theRootNode != null) {
//root
System.out.print(theRootNode.value + ",");
//left
traversePreOrder(theRootNode.left);
//right
traversePreOrder(theRootNode.right);
}
}
/**
* POST ORDER Traversal - Recursively traverses LEFT-RIGHT-ROOT
*/
public static void traversePostOrder(BinaryTreeNode theRootNode) {
if (theRootNode != null) {
//left
traversePostOrder(theRootNode.left);
//right
traversePostOrder(theRootNode.right);
//root
System.out.print(theRootNode.value + ",");
}
}
}
/**
* Binary Tree Node representation.
* - Node has a value, a left node and a right node.
* - Single node, when created, has left and right node as null.
*/
@SuppressWarnings("rawtypes")
class BinaryTreeNode {
Comparable value;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(Comparable value) {
this.value = value;
this.left = null;
this.right = null;
}
}

Output of running the above program:

IN ORDER TREE TRAVERSAL
3,5,6,7,10,12,13,15,16,18,20,23,
PRE ORDER TREE TRAVERSAL
15,5,3,12,10,6,7,13,16,20,18,23,
POST ORDER TREE TRAVERSAL
3,7,6,10,13,12,5,18,23,20,16,15,