The simplest way to represent a node, , in a binary tree is to explicitly store the (at most three) neighbours of :
class BTNode { N *left; N *right; N *parent; BTNode() { left = right = parent = NULL; } };When one of these three neighbours is not present, we set it to . In this way, both external nodes of the tree and the parent of the root correspond to the value .
The binary tree itself can then be represented by a pointer to its root node, :
Node *r; // root node
We can compute the depth of a node, , in a binary tree by counting the number of steps on the path from to the root:
int depth(Node *u) { int d = 0; while (u != r) { u = u>parent; d++; } return d; }
Using recursive algorithms makes it very easy to compute facts about binary trees. For example, to compute the size of (number of nodes in) a binary tree rooted at node , we recursively compute the sizes of the two subtrees rooted at the children of , sum up these sizes, and add one:
int size(Node *u) { if (u == nil) return 0; return 1 + size(u>left) + size(u>right); }
To compute the height of a node , we can compute the height of 's two subtrees, take the maximum, and add one:
int height(Node *u) { if (u == nil) return 1; return 1 + max(height(u>left), height(u>right)); }
The two algorithms from the previous section both use recursion to visit all the nodes in a binary tree. Each of them visits the nodes of the binary tree in the same order as the following code:
void traverse(Node *u) { if (u == nil) return; traverse(u>left); traverse(u>right); }
Using recursion this way produces very short, simple code, but it can also be problematic. The maximum depth of the recursion is given by the maximum depth of a node in the binary tree, i.e., the tree's height. If the height of the tree is very large, then this recursion could very well use more stack space than is available, causing a crash.
To traverse a binary tree without recursion, you can use an algorithm that relies on where it came from to determine where it will go next. See Figure 6.3. If we arrive at a node from , then the next thing to do is to visit . If we arrive at from , then the next thing to do is to visit . If we arrive at from , then we are done visiting 's subtree, and so we return to . The following code implements this idea, with code included for handling the cases where any of , , or is :
void traverse2() { Node *u = r, *prev = nil, *next; while (u != nil) { if (prev == u>parent) { if (u>left != nil) next = u>left; else if (u>right != nil) next = u>right; else next = u>parent; } else if (prev == u>left) { if (u>right != nil) next = u>right; else next = u>parent; } else { next = u>parent; } prev = u; u = next; } }

The same facts that can be computed with recursive algorithms can also be computed in this way, without recursion. For example, to compute the size of the tree we keep a counter, , and increment whenever visiting a node for the first time:
int size2() { Node *u = r, *prev = nil, *next; int n = 0; while (u != nil) { if (prev == u>parent) { n++; if (u>left != nil) next = u>left; else if (u>right != nil) next = u>right; else next = u>parent; } else if (prev == u>left) { if (u>right != nil) next = u>right; else next = u>parent; } else { next = u>parent; } prev = u; u = next; } return n; }
In some implementations of binary trees, the field is not used. When this is the case, a nonrecursive implementation is still possible, but the implementation has to use a (or ) to keep track of the path from the current node to the root.
A special kind of traversal that does not fit the pattern of the above functions is the breadthfirst traversal. In a breadthfirst traversal, the nodes are visited levelbylevel starting at the root and moving down, visiting the nodes at each level from left to right (see Figure 6.4). This is similar to the way that we would read a page of English text. Breadthfirst traversal is implemented using a queue, , that initially contains only the root, . At each step, we extract the next node, , from , process and add and (if they are non ) to :
void bfTraverse() { ArrayDeque<Node*> q; if (r != nil) q.add(q.size(),r); while (q.size() > 0) { Node *u = q.remove(q.size()1); if (u>left != nil) q.add(q.size(),u>left); if (u>right != nil) q.add(q.size(),u>right); } }

opendatastructures.org