Step 3 of 6

Traversals and validation

To visit every node of a tree, you choose an order. The three classic depth-first orders differ only in when the node itself is handled relative to its subtrees:

• pre-order: node, left, right (copying a tree, serializing it)
• in-order: left, node, right (a BST comes out sorted)
• post-order: left, right, node (deleting a tree, evaluating an expression tree)

#include <iostream>
#include <memory>
#include <string>

struct Node {
    std::string v;
    std::unique_ptr<Node> left, right;
};

std::unique_ptr<Node> mk(std::string v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) {
    return std::make_unique<Node>(Node{std::move(v), std::move(l), std::move(r)});
}

void pre(const Node* n)  { if (!n) return; std::cout << n->v << " "; pre(n->left.get()); pre(n->right.get()); }
void in(const Node* n)   { if (!n) return; in(n->left.get()); std::cout << n->v << " "; in(n->right.get()); }
void post(const Node* n) { if (!n) return; post(n->left.get()); post(n->right.get()); std::cout << n->v << " "; }

int main() {
    /* The expression (2 + 3) * 4 as a tree:  *
                                             / \
                                            +   4
                                           / \
                                          2   3     */
    auto root = mk("*", mk("+", mk("2"), mk("3")), mk("4"));
    std::cout << "pre:  "; pre(root.get());  std::cout << "\n";
    std::cout << "in:   "; in(root.get());   std::cout << "\n";
    std::cout << "post: "; post(root.get()); std::cout << "\n";
}

pre:  * + 2 3 4 
in:   2 + 3 * 4 
post: 2 3 + 4 * 

The three functions are identical except for where the std::cout line sits. Post-order gives reverse Polish notation, the order a calculator (or your stack evaluator from the containers module) needs: both operands before the operator.

Checking that a tree is a valid BST

A tempting check is "each left child is smaller than its parent and each right child is larger". It's a classic wrong answer:

      10
     /  \
    5    15
        /
       6        6 is left of 15 (fine locally), but it's in 10's RIGHT subtree, so it must be > 10

The correct check passes an allowed range down the tree. The root may be anything. Going left, the node's key becomes the new upper limit; going right, it becomes the new lower limit. Every node must lie strictly inside the range it inherited from all its ancestors:

is_bst(n, lo, hi):
    if n is empty: true
    if not (lo < n.key < hi): false
    return is_bst(n.left, lo, n.key) and is_bst(n.right, n.key, hi)

The limits are long so that LONG_MIN and LONG_MAX can stand for "no limit" without clashing with any int key.

Your turn: write void in_order(const Node* n, std::vector<int>& out) and bool is_bst(const Node* n, long lo, long hi) that checks all keys lie strictly between lo and hi (the test calls it with LONG_MIN, LONG_MAX).

Previous: Binary search trees Next: Level order with a queue