Course contentsShow
← Computer Science
Lesson 456 of 2,87211. Binary TreesFree lesson

Subtrees and Their Properties

Defining subtrees rooted at any node and understanding how trees are recursively composed of subtrees.

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:

  1. Doing something at the current node
  2. 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 (including N itself)
  • The depth of nodes within the subtree is measured from N as 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.