Learn Binary search trees in 20 minutes 🔍

[@BroCodez]

WARNING: THIS IS AN EXTREMELY DIFFICULT TOPIC, DO NOT GET DISCOURAGED :) public class Main { public static void main(String[] args) { //Binary Search Tree = A tree data structure, where each node is greater than it's left child, // but less than it's right. // benefit: easy to locate a node when they are in this order // time complexity: best case O(log n) // worst case O(n) // space complexity: O(n) 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.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 { // node found if(root.left == null && root.right == null) { root = null; } else if(root.right != null) { //find a successor to replace this node root.data = successor(root); root.right = removeHelper(root.right, root.data); } else { //find a predecessor to replace this node root.data = predecessor(root); root.left = removeHelper(root.left, root.data); } } return root; } private int successor(Node root) { //find least value below the right child of this root node root = root.right; while(root.left != null){ root = root.left; } return root.data; } private int predecessor(Node root) {//find greatest value below the left child of this root node 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; } }

[@RinInABin]

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

[@vinsmokesanji7629]

thank you bro

[@spenzr6920]

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

[@joyceasante8292]

(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; } }

[@zenovak5177]

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

[@DassVeryGood]

This semester my professor is terrible teacher and of course it had to be a subject that matters most in this line of work. So I just want to say thank you for saving me in this class. Even if I don’t do well in the class (it’s the most convoluted, intimidating, and egregious class I’ve ever taken and been graded on) I’m still thankful that someone can explain this concept in a straightforward manner.

[@unodos2647]

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

[@hk254lyt8]

How did you do?

You programmer now

[@super-_-chill1812]

Funny enough I took the Data Structure course a year ago and only understood trees today. Thank you Bro Code🙏🙏

[@Ran_cnc_3d]

Bro ,somewhere on 8-10 minutes I saw orcs from Warcraft 3, running on my screen. I recognized myself in childhood sitting near my old Pentium 4...Then NPC bots came and crush my base , I was so angry! And then I woke up. Such a strange dream.

[@АлександрФельдман-й8в]

Отлично! Жду ещё видео про деревья.

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

[@adamjahani4494]

I love this guy. BRO thank you. I hate my professors they don't know how to explain anything to students.

[@anonimanonim1223]

I used debugger in Eclipse IDE to understand how a program works. Very useful tool to learn programming if you do not know how something works.

[@tunamusic2314]

yuppp

[@kartikeyayadav1549]

A binary tree is a tree where each node has no more than 2 children. Root node should be greater than left child and less than right child. Leftmost child must have the least value. Right most child should have the most value. This arrangement helps with quick lookup. Big O logn

[@spacemeat23]

Best tutorial channel out there, thanks a ton

[@rabbit3711]

Bro, you are pro, the way you teach this topics is just amazing. I thought it will be imposible for me to understand trees, but you make it possible bro, thanks for what you dooo :D

[@28santagabo]

I learned a ton with your videos

[@APDesignFXP]

Bro tbh, as someone who about to start SE, it's fascinating to me how recursion used in 8:00. Truly am a geek.

[@eugenezuev7349]

sweet but tough as I can see you are not so bad at gardening, thanks Bro

[@kvelez]

Great video, always appreciate your kind words. public class App { 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(7)); tree.insert(new Node(3)); tree.insert(new Node(4)); tree.insert(new Node(6)); tree.insert(new Node(8)); tree.remove(5); tree.display(); System.out.println(tree.search(7)); } } class Node{ int data; Node left; Node right; public Node(int data){ this.data = data; } } 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 serachHelper(root, data); } private boolean serachHelper(Node root, int data){ if (root == null){ return false; } else if (root.data == data){ return true; } else if (root.data > data){ return serachHelper(root.left, data); } else { return serachHelper(root.right, data); } } public void remove(int data){ if (search(data)){ removeHelper(root, data); } else{ System.out.println( data + " could not be found."); } } public 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.left = 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, data); } else{ root.data = predecesor(root); root.left = removeHelper(root.left, data); } } return root; } private int successor(Node root){ root = root.right; while (root.left != null){ root = root.left; } return root.data; } private int predecesor(Node root){ root = root.left; while (root.right != null){ root = root.right; } return root.data; } }

[@stephanieezat-panah7750]

This was *excellent*, thank you!

[@lukhanyokalashe1906]

Thanks Bro, my Proff decided to skip this part but then in interviews i know they ask such question !! btw implementing in c# but we suing generics instead of int but implementation is the same. from SA

[@Luna-mu1wm]

this is actually a really good covering video ! nice

[@marinhoconservador]

Love you Bro, from Brazil

[@tasneemayham974]

I have a question: Instead of making successor and predecessor methods, can't we write: else if(root.right != null) return root.right; else if(root.left != null) return root.left; In the end, if a node has only one child, then we directly connect its parent with the child. Does anyone think this works?

[@XxbankerboomxX]

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

[@XxbankerboomxX]

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

[@tasneemayham974]

​@@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!!

[@XxbankerboomxX]

@@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.

[@PIRAKAS666]

shits mad hard bro

[@sirgeorgioalastrata4104]

fuck yes bro

[@El_MakAaroni]

At 18:51, i got a java.lang.NullPointerException: null highlighting hte while(root.left != null) what happened here?

[@johnwilliams-qn8mx]

I don't understand shit , your video is nice though

[@antonionotbanderas9775]

I'm only at 2:47 and need to implement these nested left right classes for my interactive fiction project. I'm happy with nodejs termux, yeah in 2024 everyone is making mobile games 🤣

[@jeffisded1222]

Doesn't your remove method not actually remove the node, but updates the value to the successor/predecessor's value, then deletes the successor/predecessor? I feel like that is a cheese way of "removing" the node. I guess it works in this example though.

[@jcesar2017]

No this is how you actually delete nodes in BSTs since you have to keep BST property once you delete that node .

[@lightninginmyhands4878]

Great job. Thanks

[@olexandrberdnikov9149]

Why search a node before removing? I mean if the node is there we will do same work twice because the removing process still involves same searching. Why not just try removing it in one attempt and if the node is not there simply return false if we need this knowledge outside of the method?

[@KaronJones-w2r]

I dont know if anyone will see this, but if all of our code is in the helper method, why cant we just use that as our method without having to call a helper?

[@Juliana-cx7qq]

bro code I promise if I remember one day I owe you a meal or a coffee, in a future when I have more money.... god I LOVE YOU MAN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[@thomas_1611]

cool video

[@stoiandelev12345678]

Отлично обяснение

[@gameGXT]

Super

[@arniequeamaba6635]

Bro was a legend

[@manishbhurtel8848]

Love from nepal

[@TAPPED_Out]

sup bai

[@chillaestheticlove7437]

Love you bro

[@princeangelo7051]

Cool

[@TAPPED_Out]

bro is R E L E L E N T L E S S

[@ricardotrejoruiz5776]

Probably the code misses when a value is insert two times... Or is it necessary to save any number even is inserted twice? I know is called binary tree but not binary list tree jajajaj

[@luciddoggo5094]

I still dont get how to even make a tree, it feels like it just went from level 1 coding to level 30 in two videos. I understood everything b4 this

[@Sammysapphira]

The tree is populated with the insert method

[@smocloud]

The tree itself is actually an amalgamation of different data types you wrap together into your own data type, or structure. In C, for example, you could do this using the “struct” keyword to create what is commonly called “nodes” that wraps your value type (it could be a character, a string, an int, whatever) and two pointers to two nodes, one to the left child node, and one to the right. In this way, you can then create a variable of your struct nodes type and create a tree by putting your value into your variable inside the node and when you need to put another one in, you compare to see if your new one you’re trying to insert is greater or less, and insert it on the right (if greater) or the left (if less). If you know how a linked list works, it shouldn’t be too hard to conceptualize a binary tree, but I’m sure you’ve got it figured out by now.

[@baljeetsingh5813]

GOAT

[@MrLoser-ks2xn]

Thanks!

[@x-yv9uv]

At 10:15 , When I Run this in a debugger the node traversal makes sense and it keeps running normally till it reaches the left most node of the tree and then i get an null node (root.left to the leftmost node with no children is null which makes sense) then it just skips to System.out.print statement without exiting the if statement ? why is that ? can someone walk me through if step by step ? shouldn't the print be outside the if statement ? it doenst make sense for me

[@tasneemayham974]

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.

[@x-yv9uv]

@@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) ?

[@tasneemayham974]

@@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.

[@tasneemayham974]

@@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!!!!!!!!!!!!!!!

[@x-yv9uv]

@@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

[@minhct2511]

Love from VietNam

[@betteryourself6653]

Chào fellow bro 😂

[@sametsahin-eh3qj]

THE GOAT

[@marke4246]

A true sigma

[@mensahtribeadventures2630]

🤓💪🏾💪🏾😎

[@HousseinAlDroubi]

Good, what about you.

[@sharkboyloga]

final boss of OOP

[@scuffedwizard]

You are a real fucking lifesaver I hope you know that

[@AibekMurat-m2z]

Bro really said Thorfinn☠

[@jatoxo]

Is it technically still a valid binary tree if you have: . 3 . / \ . 2 5 . / \ . 1 4 This way 4 is bigger than 2 and 2 is smaller than 3, so it should fit the definition, but if you were looking for 4 you would never find it

[@hritwiknauriyal2254]

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

[@brenotanquista9543]

no

[@mahaiye3903]

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

[@jarvisjackson4833]

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.

[@anotheryoutuberperson38]

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

[@mrpipiskin4]

true chad

[@felipemedrano5363]

Hello Bro

[@thuydung7028]

hi

[@MK-wc7sy]

طيب لو اقولك نتزوج

[@3bood_kr]

يو💀💀

[@MK-wc7sy]

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

[@tsunningwah3471]

swxz!

[@lequangnghi194]

I have no idea how the displayHelper() works 🥲

[@X0RZ0R]

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 😂

[@ricardotrejoruiz5776]

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 :)