So its the data structure in particular and not generics you are having problems comprehending... I see
A binary search tree is simply a tree turned upside down that's used for fast look-up... And yes its a self referential type
If you go outside and observe a physical tree carefully you would realize that's what you are trying to implement virtually in software...
A tree starts at the root and when it reaches at joint, it spans out in different directions creating alternative paths... Think of it as if you were an
ant or some small creature trying to go up a tree to get to something... You have to start at the root and when you reach a joint decide which of the alternative paths to choice from to get to your destination...
The only difference with the real tree and the virtual tree is that the virtual tree is refined in the case of a
binary tree to split into only two alternative parts when you reach a joint...
The specification for a binary search tree states that you insert an element at the root... lets use the number
7
When you want to
insert another value into the tree (
the tree grows) you make considerations... If the current value you would like to insert is greater than the value at the joint you insert the element to the right (
a branch shoots out from the joint heading to the right), if its a lesser value then you insert it to the left (
a branch shoots out from the joint heading to the left)...
So it goes as follows:
7 <- root
Would like to insert 9 which is greater than 7 so insert it into the right branch
Would like to insert 4 which is less than 7 so insert it into the left branch
Would like to insert 15 which is greater than 7 so go up the right branch which we find a 9 which is less than 15 so insert 15 into a new branch on the right
Follow this logic until you end up with a tree full of branches...
The branches containing 4 and 15 would be considered as a leaves since it does not go on any further... Just like a real tree where a leaf does not have any further extensions...