# Trees

## Table of contents

## Introduction

A tree is set of one or more nodes, where:

- There is one designated root node of the tree, .
- The remaining nodes are partitioned into disjoint sets , where each of the sets are also trees. The trees are called subtrees of .

Trees use the same terminology as family trees to describe relationships between nodes. A node can have a parent, a sibling, a grandparent, etc. [1, P. 311].

The number of subtrees of a tree is called its **degree**. A tree of degree 0 is a **leaf** [1, P. 308].

A **forest** is a set of of zero or more disjoint trees. Deleting the root of a tree creates a forest [1, P. 309].

## Representing a rooted tree

A rooted binary tree can be represented as nodes with pointers `parent`

, `left`

, and `right`

, where `parent`

points to the parent node, `left`

points to the left child node and `right`

points to the right child node [2, P. 246].

is the root of the tree if `parent`

.

*Note: future diagrams don’t show NULL pointers explicitly.*

A rooted tree node with children (an n-ary tree) can be represented using similar pointers. Instead of a pointer to each child from the parent, each node contains a `left_child`

pointer to the leftmost child (or `NULL`

if not), and a `right_child`

pointer to the right most child (or `NULL`

if ).

Each node then contains two pointers: `left_sibling`

and `right_sibling`

. `left_sibling`

points to the previous sibling (`NULL`

if none exists), and `right_sibling`

points to its immediate right sibling (`NULL`

if none exists) [2, P. 246].

## References

- [1] D. E. Knuth,
*The Art of Computer Programming*, vol. 1. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc. , 1998. - [2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
*Introduction to Algorithms*, 3rd ed. The MIT Press, 2009.