# Thread: Hi, I'm new and have a question about binary search trees and avl trees

1. Member
Join Date
Dec 2013
Posts
2
Rep Power
0

## Hi, I'm new and have a question about binary search trees and avl trees

I have some questions about certain placement of child nodes since I'm just learning BSTs and it's quite confusing even after reading some sources and doing some online insertion applets. Let's say I want to add nodes 5,7,3,4 to an empty basic BST.

Ok I understand that the left child must be less than the parent AND less than or equal to the right child from that same parent. I follow it until we add the 4 node. How do we determine that the insertion of 4 goes to the bottom right leaf position of 3 instead of the bottom left leaf position? Also, doing a AVL insertion of nodes 5,18,3,7,11 yielded some surprising position placements. Inserting the fourth node, 7, went down through 18 instead of 3. Is there a particular reason why? Assuming that is the correct way, inserting 11 would switch the 11 and 18 spots, but wouldn't having 18 as the parent node, 7 as left child, and 11 as right child adhere to the principle of left child smaller than parent and smaller or equal to right child? I'm confused! I would appreciate any help. Thank you!

insert 7

insert 11

2. ## Re: Hi, I'm new and have a question about binary search trees and avl trees

Originally Posted by Jill Ceke
Ok I understand that the left child must be less than the parent AND less than or equal to the right child from that same parent.
The way it fits in my brain is a little more basic: everything to the left of a particular node is less than that node. Everything to the right of a node is greater than that particular node. Keep that in mind for the rest of your questions.

Originally Posted by Jill Ceke
I follow it until we add the 4 node. How do we determine that the insertion of 4 goes to the bottom right leaf position of 3 instead of the bottom left leaf position?
You have a tree that consists of a 5 with a left child of 3 (because it's smaller than 5) and a right child of 7 (because it's greater than 5). You want to insert a 4, so you look at the 5. Since 4 is less than 5, you know it has to go on the left side of it. Now you look at the 3. Since 4 is greater than 3, you know it has to go on the right side of 3.

Originally Posted by Jill Ceke
Inserting the fourth node, 7, went down through 18 instead of 3. Is there a particular reason why?
Again, because 7 is greater than 5, it has to be on its right side.

3. Member
Join Date
Dec 2013
Posts
2
Rep Power
0

## Re: Hi, I'm new and have a question about binary search trees and avl trees

Originally Posted by KevinWorkman
The way it fits in my brain is a little more basic: everything to the left of a particular node is less than that node. Everything to the right of a node is greater than that particular node. Keep that in mind for the rest of your questions.

You have a tree that consists of a 5 with a left child of 3 (because it's smaller than 5) and a right child of 7 (because it's greater than 5). You want to insert a 4, so you look at the 5. Since 4 is less than 5, you know it has to go on the left side of it. Now you look at the 3. Since 4 is greater than 3, you know it has to go on the right side of 3.

Again, because 7 is greater than 5, it has to be on its right side.

OMG, I get it. Sometimes the best explanation is the simplest one. Thank you so much~

4. ## Re: Hi, I'm new and have a question about binary search trees and avl trees

No problem. Glad I could help!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•