Deletion in Binary Tree | Delete a node in Single Traversal

[@parzivallopez1272]

with this voice you can be the next big boss

[@KnowledgeCenter]

Great idea.

[@iumar28]

Came here after spending too much time. Nice Explanation. Thanks

[@venkataramana148]

I have looked for Binary Tree exlaination with code through out the internet and found your explanation so useful. thank you so much for this video.

[@KnowledgeCenter]

Glad to hear.

[@teetanrobotics5363]

Thank you so much sir. Your channel is amazing. .Need more Binary Tree and BST coding tutorials.

[@blackhatsamurai9386]

Thank you for uploading this video. Your explanation was very clear. Finally I understood this question

[@desmondodion9046]

This is a really good tutorial

[@Voice_Of_Thoughts]

your videos are really helpful please make more videos on data structures and problem solving

[@KnowledgeCenter]

Thanks.

[@aksharkashyap]

Thank you so much for your efforts. These videos are really helpful.

[@KnowledgeCenter]

Thanks.

[@sheetalray818]

Very good video with a thorough explanation

[@KnowledgeCenter]

Thanks.

[@milanapegaonkar3614]

I had been looking for deletion of node using level order traversal, I dont like the Recursion method. Thanks

[@KnowledgeCenter]

Oh. Then it's good that I used level order approach. But, you have to like the Recursion as well.

[@HarshKumar-nh6be]

I think that in the remove function there is no need of checking if root == NULL as it was already checked in the delete function. if it was null than it should be simply returned by the delete function. AFTER ALL I FOUND THIS VIDEO WHICH MAKE ME UNDERSTOOD THE DELETION OF NODE.

[@rajeetkaushal6119]

I think it's necessary since we have both side traversal(right & left). root == NULL is base condition for the side where you won't find the node that has to be deleted (e.g suppose the node that has to be deleted is in left side. Left side recursive call will delete the node, after that we have right recursive call as well which will be executed after left recursive call & since there is no node that has to be deleted you'll need some base condition to return from that call otherwise you'll be stuck in the right recursive call. I hope you get the point :)

[@HarshKumar-nh6be]

@@rajeetkaushal6119 that was already checked

[@rajeetkaushal6119]

​@@HarshKumar-nh6be test case - delete node from left subtree ( you'll get segmentation fault w/out null condition)

[@nikhilkesapure9002]

sir,
this is double traversal since we searched node whose data to be replaced by deepest node
and then we searched the deepest node parent
Is there no way we can figure out deepest node parent in optimize way using single traversal

[@AnonymousProdigy]

where can i find the src code for this???
pls reply

[@indmanish209]

your voice is very scaring sir

[@KnowledgeCenter]

Don't get scared.

[@abhishekkk95]

@@KnowledgeCenter Ya i tried
lol

[@iswitchcomputerscience7071]

JAVA Implementation :
public class DeleteNodeInBinaryTree {
public static void main(String[] args) {
BinaryTreeNode root = createBinaryTree();
inorderTraversal(root);
root = deleteNode(root,3);
inorderTraversal(root);
}
//
private static BinaryTreeNode deleteNode(BinaryTreeNode root, int data) {
BinaryTreeNode keyNode=null,lastNodeParent=null,lastNode=null;
Queue queue = new LinkedList();
queue.offer(root);
if(root == null){
return null;
}
// if root is only node and it is also key node that is to be deleted
if(root.getLeft() == null && root.getRight() == null && root.getData() == data){
return null;
}
while(!queue.isEmpty()){
lastNode = queue.poll();
if(lastNode.getData() == data){
keyNode = lastNode;
}
if(lastNode.getLeft() != null){
lastNodeParent = lastNode;
queue.offer(lastNode.getLeft());
}
if(lastNode.getRight() != null){
lastNodeParent = lastNode;
queue.offer(lastNode.getRight());
}
}
// copy last node data to key node, if keyNode is found
if(keyNode != null){
keyNode.setData(lastNode.getData());
if(lastNodeParent.getLeft() == lastNode){
lastNodeParent.setLeft(null);
}else if(lastNodeParent.getRight() == lastNode){
lastNodeParent.setRight(null);
}
}
return root;
}
/*
* 1
* 2 3
* 4 5 6 7
* */
private static BinaryTreeNode createBinaryTree() {
BinaryTreeNode head = new BinaryTreeNode(1);
BinaryTreeNode left = new BinaryTreeNode(2);
BinaryTreeNode right = new BinaryTreeNode(3);
left.setLeft(new BinaryTreeNode(4));
left.setRight(new BinaryTreeNode(5));
right.setLeft(new BinaryTreeNode(6));
right.setRight(new BinaryTreeNode(7));
head.setLeft(left);
head.setRight(right);
return head;
}
private static void inorderTraversal(BinaryTreeNode root) {
System.out.println();
Stack stack = new Stack();
stack.push(root);
while(!stack.isEmpty()){
BinaryTreeNode tmp = stack.pop();
System.out.print(tmp.getData());
if(tmp.getRight() != null){
stack.push(tmp.getRight());
}
if(tmp.getLeft() != null){
stack.push(tmp.getLeft());
}
}
}
}