# C++ Notes: Binary Tree Traversal

## Typical binary tree node

Assume these definition for the following examples.

    struct tree_node {
        tree_node *left;   // left subtree has smaller elements
        tree_node *right;  // right subtree has larger elements
        int data;
    };

## Traversing a binary tree

Traversing (visiting all the nodes) a tree starting at node is often done in one of three orders

- Preorder - node, left subtree, right subtree.
- Inorder - left subtree, node, right subtree. This could be used to print a binary search tree in sorted order.
- Postorder - left subtree, right subtree, node. This could be used to print an expression tree in reverse polish notation (postfix).

## Recursive code to print a binary search tree

By far the easiest way to print (or otherwise process) a binary tree is with a recursive function. This is one of the first uses of recursion that makes an algorithm much easier to code.

    void print_inorder(tree_node *p) {
        if (p != NULL) {
            print_inorder(p->left);  // print left subtree
            cout << p->data << endl; // print this node
            print_inorder(p->right); // print right subtree
        }
    }

## Exercises

1. Rewrite this for preorder and postorder traversals.
2. To save the cost of a call, this could test each pointer for non-NULL before making the call to process that subtree. Make this small improvement.
3. The example above prints each element of the tree. Rewrite the function to add (ie, `push_back`) data elements onto a global `vector<int> v`. The resulting vector will have all elements in sorted order as a consequence of the inorder traversal.