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