Learn-dsa..in 30 days!



























CC-1 : Implement Binary Tree.

Description:

In below sections we will code a custom Binary Tree using a LinkedList concept. AddNode() method of the Binary Tree will add the node and deleteNode() method will remove node from the Binary Tree. We will use a TreeNode class to store the individual data of the nodes and to store pointers to Child nodes. The TreeNode class below stores integer data, it can easily be modified to store String, Char, or custom classes as data.

Test cases and expected outputs:

Input Parameters Expected outputs
BinaryTree binTree=new BinaryTree(); binTree.addNode(1); binTree.addNode(2); binTree.addNode(3); binTree.addNode(4); binTree.addNode(5); binTree.addNode(6); binTree.addNode(7); binTree.addNode(8); binTree.addNode(9); retVal=binTree.bfsTraversal(); printArrayListSummary(retVal, "Bfs traversal"); Bfs traversal : 1,2,3,4,5,6,7,8,9
System.out.println("HEIGHT:"+binTree.getHeight()); System.out.println("GET LEVEL OF NODE 1:"+ binTree.getLevelOfNode(1)); System.out.println("GET LEVEL OF NODE 3:"+ binTree.getLevelOfNode(3)); System.out.println("GET LEVEL OF NODE 5:"+ binTree.getLevelOfNode(5)); System.out.println("GET LEVEL OF NODE 9:"+ binTree.getLevelOfNode(9)); HEIGHT:4 GET LEVEL OF NODE 1:1 GET LEVEL OF NODE 3:2 GET LEVEL OF NODE 5:3 GET LEVEL OF NODE 9:4
System.out.println("SIZE ITERATIVE:"+binTree.getSize()); SIZE ITERATIVE:9
System.out.println("Delete node:"+3); binTree.deleteNode(3); retVal=binTree.bfsTraversal(); printArrayListSummary(retVal, "Bfs traversal"); Bfs traversal : 1,2,9,4,5,6,7,8

Below is the code for the TreeNode java class: 

public class BinTreeNode {
		private BinTreeNode leftNode=null;
	private BinTreeNode rightNode=null;
	private int nodeData=0;

	public BinTreeNode(int data) {
		nodeData=data;
	}	
	public BinTreeNode getLeftChild() {
		return leftNode;
	}
	public void setLeftChild(BinTreeNode leftNode) {
		this.leftNode = leftNode;
	}
	public BinTreeNode getRightChild() {
		return rightNode;
	}
	public void setRightChild(BinTreeNode rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}

}

Addition of node to Binary Tree.

Pseudocode:

If Binary Tree is empty add new node as root node of Binary Tree and return, else follow steps given below.
Initialize a Queue to store Tree Nodes.
Add root node of Binary Tree to Queue.
While Queue is not empty:
o Extract current Tree Node from start of Queue.
If current Tree Node does not have a left node:
add new node as left child of current Tree Node and return true.
Else add current Tree Node to Queue.
If current Tree Node does not have a right node:
add new node as right child of current Tree Node and return true.
Else add current Tree Node to Queue.

Code:

public boolean addNode(int data) throws Exception{
	BinTreeNode newNode=newNode= new BinTreeNode(data);
	if (root==null) {
		root=newNode;
		return true;
	}
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	while (queue.size()!=0) {
		node=queue.poll();
		
		if (node.getLeftChild()!=null) {
			queue.offer(node.getLeftChild());
		}else {
			node.setLeftChild(newNode);
			return true;
		}
		if (node.getRightChild()!=null) {
			queue.offer(node.getRightChild());
		}else {
			node.setRightChild(newNode);
			return true;
		}
			
	}
	return false;
}

Deletion of node from Binary Tree.

Pseudocode:

deleteNode() method:

If the Binary Tree has only one node, the set root node variable of Binary Tree to null.
Else if the Binary Tree already has more than one nodes, then locate the node of the Binary Tree which has same data as the input node data and then delete the same:
Initialize a Queue to store Tree nodes to be processed.
Add the root node to the Queue.
While Queue is not empty execute following steps:
Extract the current node from the Queue.
If node data of current node is same as the input node data to be deleted, set variable nodeToBeDeleted to current node.
If left node of current node is not null, add the left node to the Queue.
If right node of current node is not null, add the right node to the Queue.
If nodeToBeDeleted variable is not null:
Set node data of nodeToBeDeleted to node data of currentNode.
Call deleteLastNode() method with nodeToBeDeleted as input argument

deleteLastNode() method:

Initialize a Queue to store Tree nodes to be processed.
Add the root node to the Queue.
While Queue is not empty execute following steps:
Extract the current node from the Queue.
If current node== nodeToBeDeleted:
Set current node=null.
Set nodeToDelete variable to null.
Return true.
If right node of current node != null:
If right node of current node == nodeToDelete:
Set right node of current node=null.
Set nodeToDelete variable to null.
Return true from the method.
If left node of current node != null:
If left node of current node == nodeToDelete:
Set left node of current node=null.
Set nodeToDelete variable to null.
Return true from the method.
Else add left node of current node to Queue.
Return false from the method.

Code:

public boolean deleteNode(int toDelete) throws Exception{
	if (root==null) {
		return false;
	}
	if ((root.getLeftChild()==null)&&(root.getRightChild()==null)) {
		if (root.getNodeData()==toDelete) {
			root=null;
			return true;
		}
		return false;
	}	
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	BinTreeNode nodeToBeDeleted=null;
	int lastNodeData;
	while (queue.size()!=0) {
		node=queue.poll();
		if (node.getNodeData()==toDelete)
		{
			nodeToBeDeleted=node;
		}
		if (node.getLeftChild()!=null) {
			queue.offer(node.getLeftChild());
		}
		if (node.getRightChild()!=null) {
			queue.offer(node.getRightChild());
		}			
	}
	if (nodeToBeDeleted !=null) {
		lastNodeData=node.getNodeData();
		nodeToBeDeleted.setNodeData(lastNodeData);
		deleteLastNode(node);
		return true;
	}	
	return false;
}

private boolean deleteLastNode(BinTreeNode nodeToDelete) {
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	while (queue.size()!=0) {
		node=queue.poll();
		if (node==nodeToDelete) {
			node=null;		
			nodeToDelete=null;
			return true;
		}
		if (node.getRightChild() !=null) {
			if ((node.getRightChild() == nodeToDelete)) {
				node.setRightChild(null);
				nodeToDelete=null;
				return true;
			}
			queue.offer(node.getRightChild());
		}
		if (node.getLeftChild() !=null) {
			if ((node.getLeftChild() == nodeToDelete)) {
				node.setLeftChild(null);
				nodeToDelete=null;
				return true;
			}
			queue.offer(node.getLeftChild());	
		}
	}	
	return false;
}

Get size of Binary Tree.

Pseudocode:

We can code a getSize() method to return count of elements in the Binary Tree. We have given two implementations of the getSize() method. The first method uses recursion to count the nodes of the Binary Tree. The second method uses a queue to traverse the Binary Tree and count of the nodes.

Code:

public int getSize(BinTreeNode root) {
	if (root==null) {return 0;}
	int leftSize=getSize(root.getLeftChild());
	int rightSize=getSize(root.getRightChild());
	return leftSize+rightSize+1;
}

public int getSize() {
	if (root==null) {return 0;}
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	int size=0;
	while (queue.size()!=0) {
		node=queue.poll();
		size++;
		if (node.getLeftChild()!=null) {
			queue.offer(node.getLeftChild());
		}	
		if (node.getRightChild()!=null) {
			queue.offer(node.getRightChild());
		}
			
	}
	return size;
}

Get Height of Binary Tree.

Pseudocode:

We can code a getHeight() method to return maximum height (maximum count of edges from root to leaf) in the Binary Tree. We keep traversing the Binary Tree level by level till we reach the leaf nodes. A Queue is used to store nodes to be processed at each level. We increment a variable named height at each level, till we reach the deepest leaf level.

Code:

public int getHeight() {
	if (root==null) {return 0;}
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	int height=0;
	BinTreeNode node=null;
	while (queue.size()!=0) {
		int size=queue.size();
		for(int idx=0; idx < size; idx++) {
			node=queue.poll();
			if (node.getLeftChild()!=null) {
				queue.offer(node.getLeftChild());
			}
			if (node.getRightChild()!=null) {
				queue.offer(node.getRightChild());
			}
		}
		height++;	
	}
	return height;
}

Get level of node in a Binary Tree.

Pseudocode:

We can code a getLevel() method to return level (count of edges from root to node that’s level need to be found) in the Binary Tree. We keep traversing the Binary Tree level by level till we reach the node that’s level needs to be found. A Queue is used to store nodes to be processed at each level. We increment a variable named level at each level, till we reach the node that’s level needs to be found.

Code:

public int getLevelOfNode(int toSearch) {
	if (root==null) {return 0;}
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	int level=0;
	BinTreeNode node=null;
	while (queue.size()!=0) {
		level++;
		int size=queue.size();
		for(int idx=0; idx < size; idx++) {
			node=queue.poll();
			if (node.getNodeData()==toSearch) {
				return level;
			}
			if (node.getLeftChild()!=null) {
				queue.offer(node.getLeftChild());
			}
			if (node.getRightChild()!=null) {
				queue.offer(node.getRightChild());
			}
		}
			
	}
	return 0;
}

Traversing the nodes of a Binary Tree

The next code challenges cover various ways to traverse the BinaryTree nodes such as Breadth first traversal, Post order traversal, Pre-order traversal and In-order traversal.

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us