7.3. Binary Tree as a Recursive Data Structure¶
7.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.
23
8
35
10
A node followed by a list
20
5
10
30
15
40
25
Left sub-tree is a binary tree
Right sub-tree is a binary tree
The recursive relationships used to define a structure provide a natural model for any recursive algorithm on the structure.
