Binary Tree Insertion, Deletion, Search, Traversal in Java

Basic traversal on tree is best explained on http://en.wikipedia.org/wiki/Tree_traversal .

In Order:


binary_tree_inorder

 

Pre Order:

binary_tree_preorder

 

 

Post Order:

binary_tree_postorder

 

If anything is missing in explanation, you can google it and I know you all are expert as me.
Now my part starts from here.
How to implement it in java.

Project Structure in Eclipse:

Tree_projectStructure

Node.java    (nodeInfo variable has no logical meaning, it is just for printing purpose)

package datastructure.tree;

public class Node {
	
	private Node leftNode;
	private Node rightNode;
	private int nodeValue;
	private String nodeInfo;
	
	public Node(String nodeInfo,int nodeValue){
		this.nodeInfo = nodeInfo;
		this.nodeValue = nodeValue;
	}
	
	public Node getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(Node leftNode) {
		this.leftNode = leftNode;
	}
	public Node getRightNode() {
		return rightNode;
	}
	public void setRightNode(Node rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeValue() {
		return nodeValue;
	}
	public void setNodeValue(int nodeValue) {
		this.nodeValue = nodeValue;
	}
	public String getNodeInfo() {
		return nodeInfo;
	}
	public void setNodeInfo(String nodeInfo) {
		this.nodeInfo = nodeInfo;
	}
}

 

Tree.java

package datastructure.tree;

public interface Tree {

	void insertNode(Node node);
	void deleteNode(Node node);
	Node searchNode(Node node);
	
	void inOrderTraversal(Node node);
	void preOrderTraversal(Node node);
	void postOrderTraversal(Node node);
}

 

TreeImpl.java

 

package datastructure.tree;

public class TreeImpl implements Tree{

	int tree_node_count = 0;
	public Node rootNode = null;
	
	public Node getRootNode() {
		return rootNode;
	}

	public void setRootNode(Node rootNode) {
		this.rootNode = rootNode;
	}

	public TreeImpl(Node rootNode){
		this.rootNode = rootNode;
		tree_node_count = 1;
	}

	@Override
	public void insertNode(Node node){
		Node treeNode = rootNode;
		
		while(true){
			if(node.getNodeValue()<treeNode.getNodeValue()){
				if(treeNode.getLeftNode()!=null){
					treeNode = treeNode.getLeftNode();
				}else{
					treeNode.setLeftNode(node);
					System.out.println("Node "+node.getNodeValue()+" saved at left child of node :"+treeNode.getNodeValue());
					break;
				}
			}else if(node.getNodeValue()>treeNode.getNodeValue()){
				if(treeNode.getRightNode()!=null){
					treeNode = treeNode.getRightNode();
				}else{
					treeNode.setRightNode(node);
					System.out.println("Node "+node.getNodeValue()+" saved at Right child of node :"+treeNode.getNodeValue());
					break;
				}
			}else{
				System.out.println("Duplicate Node can not be saved");
				break;
			}
		}
	}
	
	@Override
	public Node searchNode(Node node){
		Node currentNode = rootNode;
		while(currentNode!=null){
			if(currentNode.getNodeValue()==node.getNodeValue()){
				System.out.println("Node "+node.getNodeValue()+" Found");
				return currentNode;
			}else{
				if(node.getNodeValue()<currentNode.getNodeValue()){
					currentNode = currentNode.getLeftNode();
				}else{
					currentNode = currentNode.getRightNode();
				}
			}
		}
		System.out.println("Node "+node.getNodeValue()+" Not Found");
		return null;
	}


	@Override
	public void deleteNode(Node node) {
		Node previousNode =  null;
		Node currentNode = rootNode;
		
		if(node.getNodeValue()==currentNode.getNodeValue()){
			System.out.println("Your Tree is Vanished");			
		}else if(node.getNodeValue()<currentNode.getNodeValue()){
			previousNode = currentNode;
			currentNode = currentNode.getLeftNode();
		}else{
			previousNode = currentNode;
			currentNode = currentNode.getRightNode();
		}
		
		while(true){
			if(node.getNodeValue()==currentNode.getNodeValue()){
				
				
				if(currentNode.getRightNode()!=null){
					Node tempPreviousNode = currentNode;
					Node tempNode = currentNode.getRightNode();
					
					if(tempNode.getLeftNode()!=null){
						while(tempNode.getLeftNode()!=null){
							tempPreviousNode = tempNode;
							tempNode = tempNode.getLeftNode();
						}
						
						if(tempNode.getRightNode()!=null){
							tempPreviousNode.setLeftNode(tempNode.getRightNode());
							previousNode.setRightNode(tempNode);
							tempNode.setLeftNode(currentNode.getLeftNode());
							break;
						}else{
							tempNode.setLeftNode(currentNode.getLeftNode());
							tempNode.setRightNode(currentNode.getRightNode());
							previousNode.setRightNode(tempNode);
							tempPreviousNode.setLeftNode(null);
							break;
						}
					}else{
						tempNode.setLeftNode(currentNode.getLeftNode());
						previousNode.setRightNode(tempNode);
						break;
					}					
				}else if(currentNode.getLeftNode()!=null){
					previousNode.setLeftNode(currentNode.getLeftNode());
					currentNode = null;
					break;
				}else{
					currentNode = null;
					break;
				}				
			}else if(node.getNodeValue()<currentNode.getNodeValue()){
				previousNode = currentNode;
				currentNode = currentNode.getLeftNode();
			}else{
				previousNode = currentNode;
				currentNode = currentNode.getRightNode();
			}
		}
	}

	@Override
	public void inOrderTraversal(Node node) {
	
		if(node!=null){
			inOrderTraversal(node.getLeftNode());
			System.out.println("Node Value:"+node.getNodeValue());
			inOrderTraversal(node.getRightNode());
		}
	}

	@Override
	public void preOrderTraversal(Node node) {
		// TODO Auto-generated method stub
		if(node!=null){
			System.out.println("Node Value:"+node.getNodeValue());
			preOrderTraversal(node.getLeftNode());
			
			preOrderTraversal(node.getRightNode());
		}
	}

	@Override
	public void postOrderTraversal(Node node) {
		// TODO Auto-generated method stub
		if(node!=null){
			postOrderTraversal(node.getLeftNode());
			
			postOrderTraversal(node.getRightNode());
			System.out.println("Node Value:"+node.getNodeValue());
		}
	}
}

MainPractise,java

import datastructure.tree.Node;
import datastructure.tree.TreeImpl;



public class MainPractise implements Cloneable{	
	
	public static void main(String[] args) {
		
		Node node = new Node("Root Node",12);
		
		TreeImpl ti = new TreeImpl(node);
		
		Node leafNode = new Node("Leaf Node",5);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",16);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",2);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",1);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",3);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",15);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",19);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",18);
		ti.insertNode(leafNode);
		
		Node deleteNode = new Node("Leaf Node",16);
		ti.deleteNode(deleteNode);
		
		System.out.println("==============In Order Traversal===================");
		ti.inOrderTraversal(ti.getRootNode());
		System.out.println("==============Pre Order Traversal==================");
		ti.preOrderTraversal(ti.getRootNode());
		System.out.println("==============Post Order Traversal=================");
		ti.postOrderTraversal(ti.getRootNode());
		
		
		System.out.println("===================================================");
		Node searchNode = new Node("Leaf Node", 17);
		ti.searchNode(searchNode);
		
		searchNode = new Node("Leaf Node", 3);
		ti.searchNode(searchNode);
       }
}

 

 

Output:

Node 5 saved at left child of node :12
Node 16 saved at Right child of node :12
Node 2 saved at left child of node :5
Node 1 saved at left child of node :2
Node 3 saved at Right child of node :2
Node 15 saved at left child of node :16
Node 19 saved at Right child of node :16
Node 18 saved at left child of node :19
==============In Order Traversal===================
Node Value:1
Node Value:2
Node Value:3
Node Value:5
Node Value:12
Node Value:15
Node Value:18
Node Value:19
==============Pre Order Traversal==================
Node Value:12
Node Value:5
Node Value:2
Node Value:1
Node Value:3
Node Value:18
Node Value:15
Node Value:19
==============Post Order Traversal=================
Node Value:1
Node Value:3
Node Value:2
Node Value:5
Node Value:15
Node Value:19
Node Value:18
Node Value:12
===================================================
Node 17 Not Found
Node 3 Found

 

I haven’t defined any methods of isEmpty() and as such methods. So if you need one let me know.

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

Leave a Reply

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