Binary tree - Data structure

What differ a binary tree from a standard tree data structure is binary tree parent can only hold 2 children (from left side and right side).

Advantages of using a binary tree is it combines both good qualities of ordered array and linked lists.

• Fast search (Like using ordered array and binary search)
• Fast insertion/deletion (Like in a linked list)

Image obtained from : https://upload.wikimedia.org/wikibooks/en/4/41/HSE_ch5_binary_tree.png

Following figure illustrates how search/add items work on a BST.

Tree Traversal 

Since tree is not a linear data structure like array or lists or queues, there are more than one way of traversing through a tree.Tree traversal simply means that you start at a node and go through each node only once.

We have 2 kinds of traversal.(This is also valid for graphs also. In fact these traversals came from graphs because tree is a special kind of a graph. )

• Depth first traversal (also called as level order trversal)
• Breadth first travesal
• Pre order (visiting order root -> left sub tree -> right sub tree)
• In order (visiting order left sub tree -> root ->  right sub tree)
• Post order (visiting order left sub tree ->  right sub tree -> root )

Image

Breadth first(level order): A,B,C,D,E,F,G,H,I (finish each level then go to next level)
Pre order: A,B,D,E,H,I,C,F,G (Only after finishing nodes left sub tree, move to right sub tree)
In order: D,B,H,E,I,A,F,C,G (First finish nodes left and node and nodes right)
Post order: D,H,I,E,B,F,G,C,A (Unless left and right sub trees are done, dont visit middle node)

Level order traversal (Depth first) process

• Hopefully we have a root node. Otherwise how can we traverse :p 
• We can use a queue for this type of traversal.
• En-queue a node.
• Print that node or do anything with that node so it is visited.
• De-queue that node. But before de-queuing, enqueue it's child nodes to the queue.
• Do this until all the nodes are over in the BST. 

Pre order/in order/post order traversal process

•  Select a node
• Visit that node
• Then visit its left node. (If that node also has a left, process is similar)
• after visiting left node,visit its right node ( (If that node also has a left, process is similar))

In in order and post order traversals the process is similar. Only the node,left,right sequences gets changed.

Binary search tree - node - Java code (For illustration)

package BinaryTreePackage;

import java.util.LinkedList;
import java.util.Queue;

public class Node {

 int data;
 Node left;
 Node right;
 
 public Node(int data) {

  this.data = data;
 }
 
 //-----------------------------------------
 // Add nodes
 // ----------------------------------------
 public void addNode(int value)
 {
  
  if(value == data){ System.out.println("Similar values!");}
  
  if(value < data)
  {
   if( left==null ){ left = new Node(value); }
   else{left.addNode(value); System.out.println("added:" + value);}
  }
  else
  { 
   if( right==null ){ right = new Node(value);  }
   else{right.addNode(value);System.out.println("added:" + value);}
  }
  
  
 }


 //-----------------------------------------
 // Search nodes
 // ----------------------------------------
 public void search(int value) {
  
  if (data==value) {System.out.println("Item found:"+data);   }
  else if(data > value)
  {
   if (left==null) {
     System.out.println("Item not found!");
   } else {
     left.search(value);
   }
  }
  else 
  {
   if (right==null) {
     System.out.println("Item not found!");
   } else {
     right.search(value);
   }
  }
 }
 
 //-----------------------------------------
 // Depth first (level order traversal)
 // ----------------------------------------
  
 public void levelOrderTraversal(Node root)
 {
  System.err.println("Initiating level order traversal");
  
  if( root==null )System.out.println("No nodes in BST"); 
  Queue queue = new LinkedList();
  queue.add(root);
  
  while (!queue.isEmpty()) {
    
   Node current = queue.poll();
   System.out.print("-"+current.data);
   
   if(current.left != null)
   { queue.add(current.left);}


   if(current.right != null)
   { queue.add(current.right); }
  }
  
 }

 public void preOrderTraversal(Node current) {

  if (current == null) return;
  System.out.print(current.data+"-");
  
  preOrderTraversal(current.left);
  preOrderTraversal(current.right);

 }

 public void inOrderTraversal(Node current) {
  
  if (current == null) return;
  inOrderTraversal(current.left);
  System.out.print(current.data+"-");
  inOrderTraversal(current.right);

 }

 public void postOrderTraversal(Node current) {
  
  if (current == null) return;
  postOrderTraversal(current.left);
  postOrderTraversal(current.right);
  System.out.print(current.data+"-");
 }
 
 }

Binary search tree - Tree - Java code

This class's goal is to crate an object that can hold other node objects and form the tress structure along with its operation.

package BinaryTreePackage;

public class BinaryTree {

 private Node root;
 
 public BinaryTree() {
  root = null;
 }
 
 public void addNode(int value)
 {
  if(root==null){root = new Node(value); }
  else{root.addNode(value);}
 }
 
 
 public void search(int value)
 {
  if (root==null) {System.out.println("No items in BST");  }
  else{root.search(value);}
 }
 
 
 public void levelOrderTraversal()
 {
  if(root==null) return;
  else root.levelOrderTraversal(root);
 }

 public void preOrderTraversal()
 {
  System.out.println("Initiating pre order traversal");
  if(root ==null) return;
  else root.preOrderTraversal(root);
 }
 
 public void inOrderTraversal()
 {
  System.out.println("Initiating in order traversal");
  if(root ==null) return;
  else root.inOrderTraversal(root);
 }
 
 public void postOrderTraversal()
 {
  System.out.println("Initiating post order traversal");
  if(root ==null) return;
  else root.postOrderTraversal(root);
 }
 
}