Subtrees and Their Properties
You'll learn how any node in a tree can act as the root of its own smaller tree, and how this recursive structure is fundamental to understanding trees.
The Core Idea
A subtree is simply a tree formed by taking any node and considering it as the root, along with all its descendants. Every node in a tree is actually the root of its own subtree—even if that subtree contains only the node itself (when it's a leaf).
Think of it like a family tree: if you focus on any ancestor and their descendants, you've created a complete family subtree. That subset still follows all the same family relationships, just starting from a different person.
Why Subtrees Matter
The beauty of subtrees is that they reveal the recursive nature of trees. A tree is really just:
- A root node, plus
- Zero or more subtrees connected to that root
This recursive composition means any operation you perform on a tree can often be broken down into:
- Doing something at the current node
- Recursively doing the same thing on each subtree
Properties of Subtrees
When you identify a subtree rooted at node N:
- The height of that subtree is the height of node
N - The size of that subtree is the count of all nodes descended from
N(includingNitself) - The depth of nodes within the subtree is measured from
Nas the new reference point, not the original root - Every subtree is itself a valid tree with all the same structural rules
An Example
In a tree where node A has children B and C, and B has children D and E:
- The subtree rooted at B contains nodes {B, D, E}
- The subtree rooted at C contains just {C} (if C is a leaf)
- The entire tree is the subtree rooted at A
Key Takeaway: Every node is the root of a subtree containing itself and all its descendants, making trees naturally recursive structures where the same operations apply at every level.