Learn Binary search trees in 20 minutes 🔍 

I needed that warning :) Keep up the good work man

thank you bro

I doubt that I will get discouraged if I study from a teacher like you 👍 And i hope no one else gets discouraged too

(Coding along, line by line) public class Main{ public static void main(String[]args){ BinarySearchTree tree = new BinarySearchTree(); tree.insert(new Node(5)); tree.insert(new Node(1)); tree.insert(new Node(9)); tree.insert(new Node(2)); tree.insert(new Node(7)); tree.insert(new Node(3)); tree.insert(new Node(6)); tree.insert(new Node(4)); tree.insert(new Node(8)); tree.remove(0); tree.display(); } } **************************** public class BinarySearchTree { Node root; public void insert (Node node) { root = insertHelper (root, node); } private Node insertHelper (Node root, Node node) { int data = node.data; if (root == null) { root = node; return root; } else if (data < root.data) { root.left = insertHelper (root.left, node); } else { root.right = insertHelper (root.right, node); } return root; } public void display () { displayHelper (root); } private void displayHelper (Node root) { if (root != null) { displayHelper (root.left); System.out.println (root.data); displayHelper (root.right); } } public boolean search (int data) { return searchHelper (root, data); } private boolean searchHelper (Node root, int data) { if (root == null) { return false; } else if (root.data == data) { return true; } else if (root.data > data) { return searchHelper (root.left, data); } else { return searchHelper (root.right, data); } } public void remove (int data) { if (search (data)) { removeHelper (root, data); } else { System.out.println (data + " could not be found"); } } private Node removeHelper (Node root, int data) { if (root == null) { return root; } else if (data < root.data) { root.left = removeHelper (root.left, data); } else if (data > root.data) { root.right = removeHelper (root.right, data); } else { if (root.left == null && root.right == null) { root = null; } else if (root.right != null) { root.data = successor (root); root.right = removeHelper (root.right, root.data); } else { root.data = predecessor (root); root.left = removeHelper (root.left, root.data); } } return root; } private int successor (Node root) { root = root.right; while (root.left != null) { root = root.left; } return root.data; } private int predecessor (Node root) { root = root.left; while (root.right != null) { root = root.right; } return root.data; } } ************************ public class Node{ int data; Node left; Node right; public Node(int data){ this.data = data; } }

no worries bro, you teach good. I am following along in C# One thing to point out when using recurssions, name your parameters a bit differently than your fields. instead of insertHelper(Node root,....) do insertHelper(Node _root). Makes it easier in the eyes

i feel you dude. data structures and algorithms is rough, especially when the class is big and the professor is...okay at best.

How did you do?

You programmer now

yuppp

Your Russian you don't brocode you're born to code

The tree is populated with the insert method

This is my solution: Find the parent of the node to remove, example we want to remove 5: parent.right= 5 is now parent.right.right = 6 and the new parent.right.left = null is the old parent.right.left = 4. In case the child was on the parent.left, just flip it around

Please tell me if you understood what i wrote i want to know if i explain well

​@@XxbankerboomxX I am sorry, for not replying fast. I am just trying to figure it out, and I am not getting it. I get traversals, inserting, searching, but I don't get deleting. I don't understand why we have to go through the whole process, and not just return the child. I am sorry for not responding, but I didn't want to tell you that I didn't quite grasp. However, I would really appreciate it if you do try to help me out here!! And great ThANK YOU!!

@@tasneemayham974 Hey no problem :) You can essentially return the child, but the parent might have two children, so if you return the right child, the left child is now left without a parent. Solution to this is to attach the left child as a child to the right child.

sup bai

يو💀💀

@@3bood_kr بشر كيف الاختبار

I believe this is the correct logic behind the code: So we have numbers from 1 till 9 and the root of the whole tree is 5, correct? (If you don't get why the root of the entire tree is 5, tell me). The traversal is called in-order. In-Order Traversal: is a process that displays the nodes of a BST in non-decreasing order and uses recursion. We start at the root of the tree and work our way towards the left. When all the left children are done, basically you reached the left-most child and the smallest data, we will encounter a null node and hence go back to the parent. Once we hit a node TWICE we will print the data of that node, and go to the right child, then take left-child and keep taking left until it's null and so on. So, we have 5 and to the left is 1. To the left of 1 there is null so we will round back and go to 1 again. Oooh we hit 1 TWICE so we print that and go to its right child which is 2. Go left, null and we encountered 2 again so print it, and go to the right. Now, it's 3 this is the first time I see 3 so we keep going left, but to the left of 3 there is null so we round back to the parent and we see 3 again. Print it. Go to right child it's 4. 4 is a leaf, so we go back we find 3(already printed), 2(already printed), 1(already printed), 5 this is the second time, so we print 5 and go to its right child. It's a lengthy reply. But I hope I made it clear.

@@tasneemayham974 Hey Tasneem thanks for the reply. The logic and everything you explained was perfect and i already understood that before but I think you made it even clearer and better. But my issues is with logic not being shown in the code itself, the code simply does it like for example: The part where you said " we will encounter a null node and hence go back to the parent." , How does that in work in Java ? all there is in the code is that root.left is passed as an argument back to the method and that there is a print statement right after it, other wise there are no elaboration or if statements, it just works which is why it's confusing me... can you tell me how did we hit a null node twice, as in where in the program does it say If(node visited twice) do (x) ?

@@x-yv9uv You're welcome!! And I do apologize for not understanding your question first. But I get it now. Here's how the code works: REMARK: Keep in mind the process is recursive which means: Recursion 1 starts with the root node and doesn't end until all the left subtrees are traversed and the right subtrees are traversed. The traversal is done when we reach a null root in which case we will return which means go back to parent. Okay, we start with the root of the entire tree as that is the first time displayHelper() is called. This is the first recursion: Recursion1[5 is the root]. Every time you insert a root that is NOT null to the displayHelper() a recursion is started and doesn't end until all its subtrees are traversed. The first line calls displayHelper() with the root's left child as the new root. Now, 1 is the new root. Is it null? No? Recursion2 starts[1 is the root]. The left child of 1 is the new root. Is it null? Yes? Return Recursion2 which means now we are back to the root 1 and half of Recursion2 is over since we traversed its left tree and found null. We will now print the root's data. Third, assign the right child as a new root. Now, 3 is the new root. Is it null? No? Recursion3 starts[3 is the root]. Call displayHelper() again with the root's left child as the new root --> 2. Is it null? No? Recursion4 starts[2 is the root]. displayHelper() is called with 2's left child as the new root. Is it null? Yes? Return Recursion4 which means we are back to root 2 and half of Recursion4 is over. To complete the second half, we go to the right child and assign it as the new root. Is it null? Yes? Return Recursion4 which means we are back again to root 2 and all of Recursion4 is over. NOTE: If you add a print statement after the displayHelper(root.right), you will see that the leaf nodes are printed twice which means that when the recursion is OVER(the entire right tree is traversed). Now, we go back to Recursion3 which has a root of 3, and we are done half, hence print the root's data. Now, assign the right child of the root as the new root -> 4. Is it null? No? Recursion4 starts[4 is the root]. Go to the left child. Is it null? Yes? Return Recursion4 which means we go back to the parent. Thus, fully traversing the left subtree and we are left with the right. So half Recursion4 is done and we came across the root for the second time, print the root's data and assign its right child as the new root. Is it null? Yes? Return Recursion4 and now it's over as both subtrees are fully traversed. We hence go back to(return) Recursion3 with root 3. Recursion3 is also done and fully traversed. Return Recursion2 with root 1. Recursion2 is done and its left&right trees fully traversed. Return Recursion1 with root 5. Recursion1 is now half traversed. The Recursion is not over, but we did finish the left branches so now print the root's data and assign its right child as the new root. This is the best I could do with the explanation. If you understand, try to explain to me the right branch of the tree. Please tell me if I made anything vague, so that I re-explain. I hope you got it.

@@x-yv9uv By the way, Sorry I forgot to add this. But this statement where I keep repeating if the root is null, then return the recursion, is present in the code as a reverse to if(root!=null). What I mean is the IDE understands that if the condition is not satisfied return the recursion. If you're not comfortable with that, you can write else{return;} Heyy, it's okay. Don't get upset if you don't get it at first. This is what it takes for us to be great coders ONE DAYYYY!!!!! Kudos to you, my friend!!!!!!!!!!!!!!!

@@tasneemayham974 Hey, Thanks for the reply, I think i kinda got it, running it again in NetBeans Debugger and keeping the if statement in mind, i think it kinda clicked in

Chào fellow bro 😂

I don't think you are ever able to insert 4 at that spot

no

4 is greater than 3, hence when you try to insert it, it would go down the right of 3, then left of 5 . 3 . / \ . 2 5 . / / . 1 4

everything to the left of a root should be smaller, the root is 3 which is smaller than 4, it is not a binary search tree.

No, 4 would be inserted to the right of the root, 3.

At first I was also a bit boggled, would you like me to try and explain? I'm only asking cause I don't want to do it if you don't need it anymore 😂

It works like composition. First it goings as deep as the composition can, then it will be start printing from the last to the beginning. Is really confusing until you get experience imaging how composition works :)