Binary Search Tree Implementation - Java Walkthrough Assignment

Functionality we will create for this implementation of the binary search tree are:
- add
- traverse
- find
- delete

Deleting a Node from a Binary search tree is a bit tricky and takes up a large chunk of time for this video. You'll be able to learn how to 'add' a Node and traverse the tree at the beginning of the video.

[sumaiyasafdar]

Let me tell you sir this is the best vedio tutorial on BST I've watched so far. I've been searching this vedio for like a week. Finally search completed.

[juku]

Thank you! I was looking for a way to use find and finally got the simple and effective way from here. Much appreciated!

[harshaldeolekar]

Hello Trevor,
Thank you very much for the detailed explanation. I see an issue in two places:
1) As pointed out by some people below, deleteCase3(), should call deleteCase1(minNode) instead of deleteCase2(minNode).
2) We haven't set the parent of nodeToBeDeleted's both children to new Node (i.e minNode 76). Both 60 and 80 node's parents are still pointing to Node 75 which is a ghost node by this point :P

However, I was able to these changes very easily by this point of learning about the binary tree. Thank you so much once again, Trevor! (I preassume the pointed out issues are true..)

[hemantkumar]

You made me understand all the concept I was struggling from last 5 days .thanks a lot.

[u]

So much respect for your sir for uploading this video.

[matthiasplechinger]

thanks for this awesome video I needed to create a Tree for a school project and tried to solve the problem with a loop but i got null pointer exeptions all the time and this video helped me more than you can imagine :)

[tomparker]

Is it missing a test in deleteCase3, what if the minLeftTraversal node does not have a child? I tried
if (minNode.leftChild!=null || minNode.rightChild!=null)
      deleteCase2(minNode)
else
     deleteCase1 (minNode)

[moomoomilk]

I get a stack overflow error if I have my nodeToadd.data <= node.data. Why does this cause an infinite recursion? I thought it would act the same as is I just had

[futurestar]

+Trevor Page There is still some logic error in deletion function as tree.delete(25); throws StackOverflowError

[World-Through-My-Lenses]

in your tree traversal, u have added node 50, but output shows 1, 10, 25, 60, 65.... where is 50?

[RobertStjohntx]

Great video....one point that had me question was when deleting a node in case 2, the parent of the node being promoted upward was not set to its new parent. I believe it was left as a reference to the node being deleted. This would only be seen in testing after a few delete calls

[lovedeepsangha]

there is a bug in DeleteCase3
after deleting a node with 2 children
cause recursion in traversal due to the minnode may or may not have a children
so that can be overcame by using
if ((minnode.LeftChild != null) || (minnode.RightChild != null)) {
DeleteCase2(minnode); /// if minnode have right child connected to it
}
else {
DeleteCase1(minnode); if minnode does not have any child connected to it
}

Thank you author for explaining BINARY TREE

[PuneetKhanna]

Hi,
I think you are traversing the left subtree and then the right subtree

i think you could have done the below, by finding which subtree the element is going to belong to and then traverse that subtree

private Node findNode(Node search, Node node) {

if(search==null){
System.out.println("The element is not found");
//nodetobereturned=null;
return null;

}
if(node.data==search.data){
return search;
}
// which subtree you should search in
if(node.data>search.data){

return findNode(search.rightchild, node);
}
else if(node.data<search.data){
return findNode(search.leftchild, node);
}
else {
return null;
}

[Ryuk]

Have you handled deleting root? Whether you'd run into NullPointerExceptions if you try and delete root element? Just asking.

[satyaachanta]

Hello Trevor, I am Satya, it is fully helpful video, I have a question in deleteCase2 calling from deleteCase3, in this example you have chosen 75 to delete and 76 became the minNode, in that process you deleted the 76 by calling deleteCase2(76), but for 76, we have no left and right child for 76, so where we are checking that condition in deletecase2, if I am wrong in observing please let me know how to understand ?, Once again I am so thankful to you

[abhilashm]

great tutorial and implementation, thanks!! This works much cooler with getters and setters.

[edwinperez]

This walk through of BST was great. I have everything working except the fact that I can't delete more than one node at a time. Not sure if anyone else ran into this issue. Can someone please help.

[gabrielantoniosaavedramart]

hi man excellent video, ?, but how can display a message when the user try insert repeat values?, i suppose you must add one else sentence but, exactly where??

[momoknz]

would Delete case 1 need the following first?
if (nodeToDelete.parent == null)
{
nodeToDelete =null;
}

if we have only one node in the tree and that is the node we want to delete??

[Saykey]

Hello Professor,
can you please use 1080p or 720p screen resolution while recording ? it very tought to read.