Binary Tree:
A binary tree is a tree data structure in which every node has at most two children usually left and right node.
left node < parent node < right node
Binary tree gives the best case performance of O(log n) and the worst case performance of 0(n), meaning if the inputs are given in sorted sequence then the binary tree representation would be in the form of Linked List, and which is of O(n) complexity.
Binary Tree can be traversed by
Depth First Traversal(In Order, Pre Order and Post Order)
Breadth First Traversal.
DepthFirst uses Stack as Datastructure and the Breadth First uses Queue as the data structure.
The implementation is given below.
For more information please refer to
http://en.wikipedia.org/wiki/Binary_Tree
en.wikipedia.org/wiki/Tree_traversal
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
/**
* This class is a sample implementation of Binary Tree and its traversals
* @author hbalakrishnan
*
*/
public class BinaryTree {
/**
*
* Just a static class Node, which holds it value
* and references to left and right nodes
*
*/
static class Node {
private Node left;
private Node right;
private int value;
public List<Node> getChildren() {
List children = new ArrayList<Node>();
if(left != null)
children.add(left);
if(right != null)
children.add(right);
return children;
}
public Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
Node rootNode = new Node(50);
insert(rootNode, 11);
insert(rootNode, 15);
insert(rootNode, 17);
insert(rootNode, 51);
insert(rootNode, 71);
insert(rootNode, 61);
System.out.println("In Order Traversal");
printInOrder(rootNode);
// System.out.println("Pre Order Traversal");
// printPreOrder(rootNode);
// System.out.println("Post Order Traversal");
// printPostOrder(rootNode);
//bfs(rootNode);
}
/**
* Method to insert the node in the form of binary tree which satisfies the below condition
* If value is less than node.value, insert left
* If value is greater than node.value, insert right
* @param p
* @param value
*/
public static void insert(Node p, int value) {
// insert at left
if(value < p.value) {
if(p.left != null) {
insert(p.left, value);
} else {
System.out.println("Node inserted with value:"+value
+" to the left of::"+p.value);
Node newNode = new Node(value);
p.left = newNode;
}
}
// insert at right
if(value > p.value) {
if(p.right !=null) {
insert(p.right, value);
} else {
System.out.println("Node inserted with value:"+value
+" to the right of::"+p.value);
Node newNode = new Node(value);
p.right = newNode;
}
}
}
/**
* In order traversal
* Traverse left, root and right
* It is a kind of DFS, which traverses the left node first until it reaches the depth, then root
* Finally it traverses the right node
* Outcome of the traversal would be in sorted sequence
* @param node
*
* [Result: 11, 15, 17, 50, 51, 61, 71]
*/
public static void printInOrder(Node node) {
if(node != null) {
printInOrder(node.left);
System.out.println("In Order Node traversed ::"+node.value);
printInOrder(node.right);
}
}
/**
* Pre order traversal
* Traverse root, left and right
* It is a kind of DFS, which traverses the root node, left and right node
* @param node
*/
public static void printPreOrder(Node node) {
//ssSystem.out.println("Pre Order Traversal");
if(node != null) {
System.out.println("Pre Order Node traversed ::"+node.value);
printPreOrder(node.left);
printPreOrder(node.right);
}
}
/**
* Post order traversal
* Traverse left, right and root node
* It is a kind of DFS, which traverses the left , right node and root node
* @param node
*/
public static void printPostOrder(Node node) {
//System.out.println("Post Order Traversal");
if(node != null) {
printPostOrder(node.left);
printPostOrder(node.right);
System.out.println("Post Order Node traversed ::"+node.value);
}
}
/**
* This uses the the simple DFS algorithm which uses stack as the Datastructure
* without recursion
* dfs
* @param rootNode
*/
public static void dfs(Node rootNode) {
Stack<BinaryTree.Node> stack = new Stack<BinaryTree.Node>();
stack.push(rootNode);
//System.out.println("Visited Node::"+rootNode.value);
while(!stack.isEmpty()) {
Node workNode = stack.pop();
System.out.println("Visited Node::"+workNode.value);
for(int j =0; j<workNode.getChildren().size(); j++) {
Node childNode = workNode.getChildren().get(j);
if(childNode.getChildren() == null) {
System.out.println("Visited Node::"+childNode.value);
} else {
stack.push(childNode);
}
}
}
}
/**
* This uses the the simple BFS algorithm which uses queue as the Datastructure
* Here I have used LinkedList to represent Queue
* without recursion
* bfs
* @param rootNode
*/
public static void bfs(Node rootNode) {
LinkedList<BinaryTree.Node> queue = new LinkedList<Node>();
queue.add(rootNode);
System.out.println("Visited Node::"+rootNode.value);
while(!queue.isEmpty()) {
Node workNode = queue.remove();
//System.out.println("Visited Node::"+workNode.value);
for(int j =0; j<workNode.getChildren().size(); j++) {
Node childNode = workNode.getChildren().get(j);
System.out.println("Visited Node::"+childNode.value);
queue.add(childNode);
}
}
}
}
