Tree Traversals

Breadth-First Traversal
Depth-First Traversal
- Pre-order depth-first traversal the root is visited first
- Post-order depth-first traversal the root is visited last (return a node if all its children are already visited)
- In-order traversal

Breadth-First Traversal

Depth-First Traversal

We can use stacks for depth-first traversal.

For binary trees

Pre-order depth first: visit root, visit left, visit right
Pre-order depth first: visit left, visit right, visit root
In-Order depth-first: Visit left, visit root, visit right

Note: in-order traversals is only applicable to binary trees (not for N-ary trees)

template<typename Type>
void Binary_tree<Type>::in_order_traversal() const {
    if (empty()) {
        return;
    }

    left()->in_order_traversal();
    cout << retrieve();
    right()->in_order_traversal();
}

Example: Pretty Printing

class Expression_node;

void Expression_node::pretty_print() {
    if (!left()) {
        if (parent()->predence() > precedence()) {
            cout << "(";
        }
    }

    left()->pretty_print();
}



In [ ]: