TREES

The reason we traverse a binary tree is to examine each of its nodes. Traversing a binary tree means visiting each node of that tree. There are several different kinds of binary tree traversals. Different kinds of traversals visit the nodes of the tree in different orders. Many different binary tree algorithms involve traversals. For example if we wish to count the number of nodes in a tree we must visit each node. If we wish to find the largest value in each node, we must examine the value contained in each node.

There are two fundamentally different kinds of binary trees traversals--those that are depth-first and those that are breadth-first.  A depth-first tree traversal or graph search always moves as far down one branch of the tree or graph as it can. After visiting the child or neighbor in a graph, it visits the grandchild or neighbor's neighbor and so on until it reaches a leaf node.

Each of the depth-first traversals is naturally recursive, because a stack is needed to maintain a record of all of the nodes visited along any particular branch. A breadth-first tree traversal or graph search always visits both the siblings of a node, or all of its neighbors in a graph, before it visits any of its grandchildren, or neighbor's neighbors in a graph.

The path followed by each of these traversals is along the branches of the tree. Each node of the tree is visited three times during each of the depth-first traversals, once on its way down the tree, a second time coming up from the left child, and a third time coming up from the right child.

There are three different types of depth-first traversals, preorder, inorder, and postorder. A preorder binary tree traversal uses the order DLR, data--extracting the data, left and then right.

A inorder binary tree traversal uses the order LDR, left, data--extracting the data, and then right. When an arithmetic expression binary tree is traversed in inorder the arithmetic expression is generated in infix notation.

A postorder binary tree traversal uses the order LRD, first left, then right, then data--extracting the data. When an arithmetic expression binary tree is traversed in postorder the arithmetic expression is generated in postfix notation. When an arithmetic expression binary tree is traversed in preorder the arithmetic expression is generated in prefix notation.

The preorder traversal extracts the value the first time it visits the node. The value of the node is copied to the list at the bottom of the screen when the value is extracted. During the inorder traversal, the value is extracted during the second visit to the node. During the postorder traversal, the value is extracted during the third visit.

There is only one kind of breadth-first traversal--the level order traversal. A level order traversal always visits the nodes of the tree, level by level. It begins at the root and proceeds top down. It visits the nodes on each level from left to right. Unlike the depth-first traversals, this traversal does not follow the branches of the tree.

To implement a level-order traversal, we need a first-in first-out queue--not a stack. A first-in first-out queue is a data structure that has two operations, enqueue, adding to the queue and dequeue, removing from the queue. The essential property of such a queue is that the first element enqueued in the first element dequeued.

A stack is a data structure that has two operations, push, adding to the stack and pop, removing from the stack. The essential property of such a stack is that the last element pushed in the first element popped.

All binary tree traversals, regardless of the order that they visit the nodes, are linear with respect to the number of number of nodes in the tree.