To find the maximum height of a 2-3 Tree, can you keep traversing from the root node to its left child node, going all the way down until you run into a leaf?
This is fact: Since all leaf-nodes are on the same height, the lowest leaf at any point is the maximum height of the tree. (All leaf-nodes are on the same level).
If you keep going left do you always reach the bottom?
Note that 2-3 Trees are balanced, which means each sub-tree (Left,Center,Right) will contain close to same amount of data - considering this statement, we can assume that traversing till the leaf-node (in any of the sub-tree) will give you the height of the 2-3 tree.
Owing to the balance of the tree, we can also say that all operations tend to be O(lg n)
.
UPDATE:
A 2-3 Tree is a null tree (zero nodes) or a single node tree (only one node) or a multiple node tree with the following properties:
- Each interior node has two or three children
- Each path from the root to a leaf has the same length.
From CS dept, IISc: http://lcm.csa.iisc.ernet.in/dsa/node118.html