A leaf is a tree node with no child links. Think of it as an endpoint on a branching path: it stores a value but does not lead to another node. Nodes with children are internal nodes. section 11.2
Leaves matter because they mark the ends of tree structure:
- In a well-formed tree, every path from the root eventually reaches a leaf without visiting the same node twice. section 11.2
- In a binary tree, a leaf has neither a left nor a right child; nodes with one or two children are internal nodes. section 11.20
- A leaf is a valid subheap of height zero, making leaves the starting building blocks for bottom-up heap construction. section 10.19
Deleting a leaf
Deleting a leaf is the simplest tree-deletion case because it has no child links to reconnect. After finding the leaf and its parent, sever the link from the parent to that leaf. If the leaf is also the root, removing it leaves an empty tree. section 11.11
