template <typename T>
class BinaryTreeNode {
T item;
BinaryTreeNode *parent;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
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:

A parent pointer.

A left pointer.

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


Each node also has a key (or item) reference.
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:

Preorder traversal: node, left, right.

Postorder traversal: left, right, node.

Inorder traversal: left, node, right.

Levelorder traversal: start at root, go down each level left to right.


Preorder, postoder and inorder traversals are examples of depthfirst search. Levelorder traversal is an example of breadthfirst search.
PreOrder Traversal

In the preorder 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)
PostOrder Traversal

In the postorder 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)
InOrder Traversal

In the inorder 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)
LevelOrder Traversal

In the levelorder 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 reconstructed 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 preorder traversal.