Binary Tree: A recursive structure

  • Recognize the recursive nature of the tree structure.

A binary tree is a recursive structure. You can imagine there is a left and a right subtree to the sides of the root, each with their own root and left/right subtrees, each with their own root and $\dots$

In a tree $T$, a node $n$ together with all of its descendants, if any, is called a subtree of $T$. Node $n$ is the root of its subtree.

The recursive structure of the tree lends itself to a recursive implementation of operations on it.

Resources