I understand that a binary search tree is a graph with rules and how it’s used in coding but relaying it in math terms is confusing me
In: 0
Do you want ELI5 or graph theoretic terms?
If you want graph theory, best to go to r/askmath ; but in simple terms it is a tree where each parent has at most two children, and the children are identified as left child and right child. The left child’s value is always less than or equal to the parent’s value, which is always less than or equal to the right child’s value.
That’s the full graph theoretic description – from there you can start to form efficient algorithms for search, hence the “search” in the name.
For ELI5: imagine you have a list of items that’s been prearranged by some value ordering. How would you find an item of a particular desired value? You might start by looking somewhere in the middle of the list – if it’s greater than your value, then you know it’s somewhere prior to the place you looked, and you’d next try somewhere near the middle of that section, etc.
What I have described is a binary search of a sorted list. If you were to connect the possible paths of searches that may result from any particular desired value with an edge, the resulting shape is a binary search tree. ie a binary search tree encodes this algorithm in terms of what “somewhere near the middle” means for any particular section.
Latest Answers