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);
		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,

Tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *