Generally, the easiest way to represent a node, u, in a binary tree is to explicitly store its three neighbours, left, right and parent. Whenever one of these neighbouring nodes is not present we set it to null. So, both the external nodes of the tree and the parent of the root are null values. The binary tree itself can therefore be represented by a reference to its root node, r. We can compute the depth of a node, u, by counting the number of step on the path from u to the root.

It is simple enough to compute facts about binary trees recursively. As an example, we can compute the size of (number of nodes in) a binary tree rooted at node u by recursively computing the size of the two subtrees rooted at the children of u, sum up these sizes and add one (see Fig.1).

Similarly, computing the height of a node, u, is achieved by computing the height of u's two subtrees, taking the maximum and adding one (see Fig.2)

Both of the two previous algorithms use recursion to visit all of the nodes in a binary tree. Each visiting the nodes of the binary tree in the order illustrated in Figure 3:

The recursion is short and simple but can become problematic, because the maximum depth of the recursion is dictated by the maximum depth of a node in the binary tree (the tree's height). So, if the height of the tree is very large, then this recursion could very cause a stack overflow and crash the application.

Perhaps the most obvious solution then, is to traverse the binary tree without recursion. This can be achieved by implementing an algorithm that depends on where it came from in order to determine the next step (see Fig.4). If we a arrive at a node, u, from u.parent we should then visit u.left. If we arrive at u from u.left we should then visit u.right and, if we arrive at u from u.right then we have finished visiting u's subtree and can return to u.parent. Whether the visit has been successful or not (null values) is indeterminate to the algorithm and dealt with via simple null checks.

The same facts that were computed recursively can also be computed non-recursively. As an example, to compute the size of the tree we keep a counter, n, and increment n whenever we visit a node for the first time. In some implementations of binary trees the parent field is not used. In this case, a non-recursive implementation is handled using a list or stack to track the path from the current node to the root.

An alternate method of traversal that does not fit the pattern of the above functions. In a breadth-first traversal, the nodes are visited level-by-level, moving down from the root and visiting each node left to right (see Fig.5). Breadth-first traversal is implemented using a queue, q, that initially contains only the root, r. At each step we extract the next node, u, from q, process u and add u.left and u.right (if they are non-null) to q.