Binary Tree and Tree Traversals using Java


    The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.A leaf node has no children.
    The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.
    The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.
    Siblings are nodes that share the same parent node.
    A node p is an ancestor of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p.
    The size of a node is the number of descendants it has including itself.
    In-degree of a node is the number of edges arriving at that node.
    Out-degree of a node is the number of edges leaving that node.
    The root is the only node in the tree with In-degree = 0.

BInary Tree

TreeNode Class


public class TreeNode{

	TreeNode leftNode;
	TreeNode rightNode;
	int data;
	
	public TreeNode(int value){
		data = value;
		leftNode = rightNode = null;
	}
	
	public void insert(int value){
		if (value < data){
			if (leftNode == null)
				leftNode = new TreeNode(value);
			else
				leftNode.insert(value);
		}
		else if (value > data){
			if (rightNode == null)
				rightNode = new TreeNode(value);
			else
				rightNode.insert(value);
		}
	}

}

Preorder Traversal

  preorder(node)
  if node = null then return
  print node.value
  preorder(node.left) 
  preorder(node.right)

Preorder Traversal

Postorder Traversal

  postorder(node)
  if node = null then return
  postorder(node.left)
  postorder(node.right)
  print node.value

PostOrder Traversal

Inorder Traversal

  inorder(node)
  if node = null then return
  inorder(node.left)
  print node.value
  inorder(node.right)

Inorder Traversal

Queue based Level order Traversal

levelorder(root) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

Level Order

Tree Class


public class Tree {

	private TreeNode root;
	
	Queue queue = new Queue();
	
	public Tree(){
		root = null;
	}
	
	public void insertNode(int value){
		
		if ( root == null)
			root = new TreeNode(value);
		else
			root.insert(value);
	}
	
	public void preorderTraversal(){
		preorder(root);
	}
	
	public void inorderTraversal(){
		inorder(root);
	}
	
	public void postorderTraversal(){
		postorder(root);
	}
	
	public void levelorderTraversal(){
		levelorder(root);
	}
	
	public void levelorder(TreeNode node){
		if (node == null)
			return;

		if (node == root)
			queue.offer(node);
		
		if (node.leftNode != null)
			queue.offer(node.leftNode);
		if (node.rightNode != null)
			queue.offer(node.rightNode);
		
		System.out.printf("%d ", queue.poll().data);
		
		levelorder(queue.peek());
	}
	
	public void preorder(TreeNode node){
		
		if (node == null)
			return;
		
		System.out.printf("%d ", node.data);
		preorder(node.leftNode);
		preorder(node.rightNode);
		
	}

	public void postorder(TreeNode node){
		
		if (node == null)
			return;
		
		postorder(node.leftNode);
		postorder(node.rightNode);
		System.out.printf("%d ", node.data);
	}

	public void inorder(TreeNode node){
		
		if (node == null)
			return;
		
		inorder(node.leftNode);
		System.out.printf("%d ", node.data);
		inorder(node.rightNode);
	}

}

TreeTest Class

import java.util.Random;


public class TreeTest {

	public static void main(String[] args){
		Tree tree = new Tree();
		int value;
		Random random = new Random();
		
		System.out.println("Inserting values");
		for (int i=1; i<=10;i++){
			value=random.nextInt(100);
			System.out.printf("%d ", value);
			tree.insertNode(value);
		}
		System.out.println();
		System.out.println("Preorder");
		tree.preorderTraversal();
		System.out.println();
		System.out.println("Postorder");
		tree.postorderTraversal();
		System.out.println();
		System.out.println("Inorder");
		tree.inorderTraversal();
		System.out.println();
		System.out.println("Levelorder");
		tree.levelorderTraversal();
	}
}

Of course, you need the Queue DS for level order traversal.


import java.util.ArrayList;
import java.util.List;


public class Queue {

	private List qlist;
	
	public Queue(){
		qlist = new ArrayList();
	}
	
	public void offer(TreeNode o){
		if (qlist.isEmpty())
			qlist.add(0, o);
		else
			qlist.add(qlist.size(), o);
	}
	
	public TreeNode poll(){
		if (qlist.isEmpty())
			return null;
		else
			return qlist.remove(0);
	}
	
	public TreeNode peek(){
		if (qlist.isEmpty())
			return null;
		else
		return qlist.get(0);
	}
}

And finally the output

Inserting values
87 77 81 89 4 26 23 27 57 1 
Preorder
87 77 4 1 26 23 27 57 81 89 
Postorder
1 23 57 27 26 4 81 77 89 87 
Inorder
1 4 23 26 27 57 77 81 87 89 
Levelorder
87 77 89 4 81 1 26 23 27 57 
Advertisements
Binary Tree and Tree Traversals using Java

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s