# 12.3. Binary Tree as a Recursive Data Structure¶

## 12.3.1. Binary Tree as a Recursive Data Structure¶

A *recursive data structure* is a data structure that is partially
composed of smaller or simpler instances of the same data structure.
For example, *linked lists* and
*binary trees* can be viewed as recursive
data structures.
A list is a recursive data structure because a list can be defined as
either (1) an empty list or (2) a node followed by a list.
A binary tree is typically defined as
(1) an empty tree or
(2) a node pointing to two binary trees, one its left child and the
other one its right child.

The recursive relationships used to define a structure provide a natural model for any recursive algorithm on the structure.