# Trees

• A tree is an abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

• As a data structure implementing that ADT, a tree is a graph (a set of nodes and edges that connect them).

• The nodes are connected is such a way that there is exactly one path between any two nodes.

• In a rooted tree, each node can have zero or more children. Each node has one parent, except for the root, which has no parents.

• Here are some more definitions:

• A leaf is a node with no children.

• An internal node is a node that is not a leaf. In other words, it is a node that has one or more children.

• Two nodes are siblings if they have the same parent. The root cannot have any siblings.

• The ancestors of a node $d$ are the nodes on the path from $d$ to the root. These include $d$, $d$'s parent, $d$'s parent’s parent and so on up to the root. The root is an ancestor of every node in the tree.

• If $a$ is an ancestor of $d$, then $d$ is a descendant of $a$.

• The length of a path is the number of edges in the path.

• The depth of a node $n$ is the length of the path from $n$ to the root. The depth of the root is zero. The depth of any node is the depth of its parent + 1.

• The height of a node $n$ is the length of the path from $n$ to its deepest descendant. In other words, it is the longest path from $n$ to a leaf. The height of a leaf node is zero. The height of an internal node is the largest height among its children + 1.

• The height of a tree is the height of the root, also the depth of the tree’s deepest node.

• The subtree rooted at node $n$ is the tree formed by $n$ and its descendants.

• A binary tree is a tree in which no node has more than two children, and every child is either a left child or a right child, even if it’s the only child its parent has.

## Binary Tree Representation

• A binary tree is a rooted tree wherein no node has more than two children. Additionally, every child is either a left child or a right child of its parent, even if it is its parent’s only child.

• In the most popular binary tree representation, each tree node has three pointers to neighboring tree nodes:

1. A parent pointer.

2. A left pointer.

3. A right pointer.

(For some algorithms, the parent pointers are unnecessary.)

• Each node also has a key (or item) reference.

template <typename T>
class BinaryTreeNode {
T item;
BinaryTreeNode *parent;
BinaryTreeNode *left;
BinaryTreeNode *right;
};

To represent the tree, we have a pointer to the node that is the root of the tree. We can also keep track of the tree’s size with an integer.

template <typename T>
class BinaryTree {
BinaryTreeNode<T> *root;
int size;
};
• We sometimes represent trees in other ways. For example, we use an array to represent a binary heap, which is based on a complete binary tree. To represent disjoint sets, we can use an array with links only from children to parents.

## Traversals

• A traversal is an algorithm (often defined recursively) to visit each node in a tree once.

• Traversals can be used in many applications: printing each node’s value or performing some calculation on all nodes, for example.

• There are four main ways to traverse the nodes of a tree:

• Pre-order traversal: node, left, right.

• Post-order traversal: left, right, node.

• In-order traversal: left, node, right.

• Level-order traversal: start at root, go down each level left to right.

• Pre-order, post-oder and in-order traversals are examples of depth-first search. Level-order traversal is an example of breadth-first search.

### Pre-Order Traversal

• In the pre-order traversal, we first visit the root and then recursively traverse the root’s children from left to right.

• An application is printing the structure of a file directory.

• Pseudocode for binary trees:

preOrder(node):
if node ≠ nil:
visit(node.key)
preOrder(node.left)
preOrder(node.right)

### Post-Order Traversal

• In the post-order traversal, we recursively traverse the root’s children from left to right subtree and then we visit the root itself.

• An application is summing the disk space taken by directories.

• Pseudocode for binary trees:

postOrder(node):
if node ≠ nil:
postOrder(node.left)
postOrder(node.right)
visit(node.key)

### In-Order Traversal

• In the in-order traversal, we first recursively traverse the root’s left subtree (rooted at the left child), then we visit the root itself, then traverse the root’s right subtree.

• This traversal is specific to binary trees.

• An application is an expression tree with infix operators.

• Pseudocode for binary trees:

inOrder(node):
if node ≠ nil:
inOrder(node.left)
visit(node.key)
inOrder(node.right)

### Level-Order Traversal

• In the level-order traversal, we first visit the root, then all nodes with depth 1, then all nodes with depth 2, etc.

• This traversal is not a naturally recursively algorithm.

• An application is finding the shortest path between two nodes (if the path length is measured by the number of edges).

• Another application is serialization/deserialization of a binary tree (as opposed to serialization in sorted order), allowing the tree to be re-constructed in an efficient manner.

• Pseudocode for binary trees, using a queue:

levelOrder(node):
q = empty queue
q.enqueue(node)
while q is not empty:
node = q.dequeue()
visit(node)
if node.left ≠ nil:
q.enqueue(node.left)
if node.right ≠ nil:
q.enqueue(node.right)

Interestingly, if we use a stack instead of a queue and push children onto the stack from right to left instead of from left to right, we will get pre-order traversal.