Picture a tree branch: choose one node, and keep everything growing below it. That portion is a subtree. Its chosen node is the subtree’s root, and every child of a node begins another subtree. section 11.2
Use the tree figure to see how selecting a node includes that node and all descendants beneath it. section 11.2
In binary trees and binary search trees, subtrees provide the structure behind familiar operations:
- A binary tree has a left subtree and a right subtree, although the ordering of those children does not always matter. section 11.4
- In a binary search tree, every value in a node’s left subtree is no greater than the node’s value, while values in its right subtree are greater. section 11.8 section 11.20
- Search uses these constraints to discard the subtree that cannot contain the target, following only one possible path at each node. section 11.8
- Because each subtree of a binary search tree is itself a valid binary search tree, maximum and minimum searches can be applied to any subtree. section 11.9
Finding an extreme value
To find the maximum in a subtree, start at its root and repeatedly follow right-child links until reaching a node without a right child. Follow left-child links instead to find the minimum. section 11.9 section 11.9
