Let B be a B-tree of order m, containing N items. Prove by induction that B has N+1 leaves.
I know that you should use induction on the depth of the tree, but how?
EDIT: The properties of a B-Tree of order m are:
- Every node has at most m children
- Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes
- The root has at least two children if it is not a leaf node
- A non-leaf node with k children contains k − 1 keys
- All leaves appear in the same level