## Binary Tree Representation and Tree Traversal (In-Order, Pre-Order, Post-Order)

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:

1. Insert Erase – O(h) where h = height
2. Lookup / Indexing – O(h)
3. 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);
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,
```