Memory refresher/My understanding:
A 2-3 tree is a balanced search tree that allows two types of nodes.
2-node: Normal node with two children.
- LChild < Parent and RChild > Parent
3-node: Node with two parents and three children.
- Parent1 < Parent2
- LChild < Parent1, Parent1 < MChild < Parent2, RChild >Parent2
A 2-3 tree is always balanced, and grows when the root raises the height of the tree by one.
My question is then as follows, given n distinct keys, how many different 2-3 trees can one construct?
My math skills are poor, so if anyone knows how I should "math" in order to approach an answer, then that would be awesome! :)