An internal node is a tree node with at least one child. Nodes without children are leaves; therefore, every non-leaf node is internal. The root can also be an internal node when it has children. section 11.2
Use these relationships to recognize internal nodes:
- A parent is an internal node whenever it has one or more children. section 11.2
- In a binary tree, an internal node has either one or two children, connected through left and right links. section 11.20
- Each child of an internal node begins a subtree, so internal nodes mark branching points in hierarchical data. section 11.2
Internal nodes in heapify
When an array is viewed as an almost-complete binary tree, leaves already form valid subheaps. Only internal nodes can violate heap properties, so heapify processes those nodes from the lowest level upward and pushes down a violating root. In the example, the internal node at index 3 is fixed first, followed by the node at index 2. section 10.19
