BST Traversals: Inorder, Preorder, Postorder (and Rebuilding the Tree)

Vocabulary you need before anything else

Get these fixed, because most confusion in traversal questions is really terminology confusion.

• Root — the single node with no parent. A tree with no nodes (an empty tree, represented by a null pointer) has no root; that is the base case of essentially every function you will write.
• Leaf — a node with no children. Not "a node at the bottom", and definitely not "a node with one child". A node with exactly one child is an internal node.
• Subtree — any node together with everything below it. The point of recursion on trees is that a subtree is itself a tree, so the same function handles it.
• Depth of a node — number of edges from the root down to it. The root has depth 0.
• Height of a node — number of edges on the longest downward path to a leaf. A leaf has height 0. The height of the tree is the height of the root.
• Height of an empty tree = -1 under this (edge-counting) convention. Some textbooks count nodes instead, making a leaf height 1 and an empty tree height 0. Both are fine; what is not fine is mixing them halfway through a question. Say which one you are using and stay there. The edge convention has the pleasant property that height = -1 makes the recurrence 1 + max(left, right) work with no special cases.
• Balanced — informally, height stays around log₂ n. A plain BST offers no such guarantee.

The BST invariant is a statement about entire subtrees, not about immediate children. "Left child smaller, right child bigger" at every node is necessary but not sufficient. A tree can satisfy the local test everywhere and still be broken globally — see the mistakes section for a three-line counterexample.

The node type used throughout this page:

struct Node {
    int   key;
    Node* left  = nullptr;
    Node* right = nullptr;
    explicit Node(int k) : key(k) {}
};

int height(const Node* n) {
    if (n == nullptr) return -1;                 // empty tree: -1 edges
    return 1 + std::max(height(n->left), height(n->right));
}

int countLeaves(const Node* n) {
    if (n == nullptr) return 0;
    if (n->left == nullptr && n->right == nullptr) return 1;
    return countLeaves(n->left) + countLeaves(n->right);
}

The three traversals: one line moves, everything changes

Each traversal does the same three things — visit the node, recurse left, recurse right — and differs only in where "visit" sits.

• Preorder — node, left, right. Root first.
• Inorder — left, node, right. Root in the middle.
• Postorder — left, right, node. Root last.

The names describe the position of the node relative to its subtrees. Left always precedes right in all three. That gives you two instant sanity checks on any answer: the first element of a preorder is the root, and the last element of a postorder is the root.

Run the code below on the tree built by inserting 50, 30, 70, 20, 40, 60, 80 in that order:

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80

The program prints:

pre : 50 30 20 40 70 60 80
in  : 20 30 40 50 60 70 80
post: 20 40 30 60 80 70 50

Read them against the definitions. Preorder announces 50 before descending. Inorder finishes the whole left subtree (20 30 40) before printing 50. Postorder prints 50 only after both subtrees are fully done.

A fourth order, level-order (breadth-first), is not a variant of these — it uses a queue rather than the call stack and visits by depth: 50, 30, 70, 20, 40, 60, 80.

The iterative inorder below is worth learning as well, because it is the standard way to build a BST iterator and it makes the "push down the left spine, pop, then go right" structure explicit.

void preorder(const Node* n, std::vector<int>& out) {
    if (!n) return;
    out.push_back(n->key);
    preorder(n->left,  out);
    preorder(n->right, out);
}

void inorder(const Node* n, std::vector<int>& out) {
    if (!n) return;
    inorder(n->left,  out);
    out.push_back(n->key);
    inorder(n->right, out);
}

void postorder(const Node* n, std::vector<int>& out) {
    if (!n) return;
    postorder(n->left,  out);
    postorder(n->right, out);
    out.push_back(n->key);
}

// Same output as inorder(), but with an explicit stack instead of recursion.
std::vector<int> inorderIterative(const Node* root) {
    std::vector<int>       out;
    std::stack<const Node*> st;
    const Node* cur = root;
    while (cur != nullptr || !st.empty()) {
        while (cur != nullptr) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        out.push_back(cur->key);
        cur = cur->right;
    }
    return out;
}

// Breadth-first, for contrast: uses a queue, not the call stack.
std::vector<int> levelOrder(const Node* root) {
    std::vector<int> out;
    if (!root) return out;
    std::queue<const Node*> q;
    q.push(root);
    while (!q.empty()) {
        const Node* n = q.front(); q.pop();
        out.push_back(n->key);
        if (n->left)  q.push(n->left);
        if (n->right) q.push(n->right);
    }
    return out;
}

Why inorder sorts, and why postorder destroys

These are not arbitrary conventions. Each order is the unique correct choice for a particular class of job.

Inorder on a BST yields ascending order. Proof by induction on the number of nodes. An empty tree emits nothing, which is trivially sorted. For a node v, inorder emits (inorder of left subtree)(v)(inorder of right subtree). By the induction hypothesis the two subtree outputs are individually sorted. The BST invariant says every key in the left subtree is < v.key and every key in the right subtree is > v.key. So the concatenation is sorted at both joints, and therefore sorted overall. Done. Note where the invariant was used: it had to be the whole subtree, not just the child — which is precisely why the local-only BST check is wrong.

Two useful consequences: an inorder walk of a BST is an O(n) sort of its keys (this is "tree sort"), and it is how std::map iteration produces keys in order. Also, if an inorder walk of something you believe is a BST comes out unsorted, you have a bug in insertion or deletion — this is the cheapest possible validity test.

Postorder is the only safe order for freeing a tree. delete n invalidates n->left and n->right; reading them afterwards is undefined behaviour, and the sanitizer will call it a heap-use-after-free. Postorder visits both children before the node, so by the time you free a node you no longer need any of its pointers. Preorder teardown either crashes or leaks; inorder teardown frees the node between its two subtrees, so the right subtree becomes unreachable — a leak of everything on that side.

Preorder is the natural order for building and copying. To clone or deserialise a tree you must create the parent before you can attach children to it. Preorder produces exactly that order, which is why clone and buildFromPre... are preorder-shaped, while destroy, height, countLeaves and "count nodes" are postorder-shaped: those aggregate information upward from children, so children must be finished first.

A compact rule: information flowing down the tree → preorder; information flowing up the tree → postorder; order along the keys → inorder.

// Preorder shape: create the parent, then attach cloned children.
Node* clone(const Node* n) {
    if (n == nullptr) return nullptr;
    Node* c = new Node(n->key);
    c->left  = clone(n->left);
    c->right = clone(n->right);
    return c;
}

// Postorder shape: children are gone before the parent's pointers die.
void destroy(Node* n) {
    if (n == nullptr) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
}

// WRONG - use-after-free. Do not do this.
// void destroyBad(Node* n) {
//     if (!n) return;
//     delete n;                 // n->left / n->right are now dangling
//     destroyBad(n->left);      // reads freed memory
//     destroyBad(n->right);
// }

Insert, search, and the three cases of delete

Insert and search are the easy half: compare, go left or right, stop. The recursive insert below returns the (possibly new) subtree root, and the caller reassigns its own pointer to it. That root->left = insert(root->left, key) idiom is what makes the code short — the alternative is tracking a parent pointer and remembering which side you came from, which is where hand-written versions usually go wrong.

Delete has three cases, distinguished by how many children the target currently has:

1. Leaf (0 children). Unlink from the parent and delete. In the code this is subsumed by the next case: root->left == nullptr is true, so we return root->right, which is also null.
2. One child. Splice: the parent adopts the node's only child. You cannot just free the node — its subtree would leak and the parent would dangle.
3. Two children. You cannot remove the node itself without orphaning a subtree, so instead you overwrite its key with its inorder successor's key and then delete the successor. The inorder successor is the next key in sorted order: the leftmost node of the right subtree. Choosing it is not arbitrary — it is the smallest key still larger than everything in the left subtree and smaller than everything else in the right subtree, so dropping it into the vacated slot preserves the invariant exactly. Crucially, the successor has no left child (it is the leftmost), so removing it is always case 1 or case 2. The recursion bottoms out; it never loops back into case 3.

The inorder predecessor (rightmost node of the left subtree) works equally well and is a valid alternative answer — pick one and be consistent, or alternate to reduce drift in height.

One subtlety in case 3: the successor may be the right child itself (when the right child has no left subtree). The code handles it with no special case, because erase(root->right, succ->key) then matches at the top of that subtree and takes the one-child/leaf branch.

Duplicates: this implementation ignores re-inserted keys. Any policy is acceptable (reject, count, or always-go-right) but it must be stated, because deletion behaviour and reconstruction from traversals both depend on it.

Node* insert(Node* root, int key) {
    if (root == nullptr) return new Node(key);
    if (key < root->key)      root->left  = insert(root->left,  key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                       // duplicate key: ignore
}

const Node* find(const Node* root, int key) {
    while (root != nullptr && root->key != key)
        root = (key < root->key) ? root->left : root->right;
    return root;                       // nullptr if absent
}

Node* minNode(Node* n) {               // leftmost node of a non-empty subtree
    while (n->left != nullptr) n = n->left;
    return n;
}

Node* erase(Node* root, int key) {
    if (root == nullptr) return nullptr;              // key not present

    if (key < root->key) {
        root->left = erase(root->left, key);
    } else if (key > root->key) {
        root->right = erase(root->right, key);
    } else {
        // Cases 1 and 2: zero or one child.
        if (root->left == nullptr) {
            Node* r = root->right; delete root; return r;
        }
        if (root->right == nullptr) {
            Node* l = root->left;  delete root; return l;
        }
        // Case 3: two children. Copy the inorder successor's key up,
        // then delete the successor from the right subtree.
        Node* succ  = minNode(root->right);
        root->key   = succ->key;
        root->right = erase(root->right, succ->key);
    }
    return root;
}

Complexity, and why it is O(h) rather than O(log n)

Everything key-based is O(h), where h is the tree's height. Writing O(log n) is only correct if you also state that the tree is balanced. The bounds on h for n nodes are ⌊log₂ n⌋ ≤ h ≤ n − 1.

• Best/typical case, h ≈ log₂ n. Randomly ordered insertions give expected height Θ(log n), so a BST behaves well on unstructured data.
• Worst case, h = n − 1. Insert already-sorted keys (1, 2, 3, 4, 5) and every node becomes a right child. You have built a singly linked list with extra pointers: search degrades to O(n) and, with deep recursion, you can blow the call stack. Sorted or reverse-sorted input is a common real-world pattern (timestamps, auto-increment IDs), which makes this failure mode far more likely in practice than "worst case" suggests.

That degeneracy is the whole motivation for self-balancing trees. An AVL tree keeps subtree heights within 1 of each other via rotations; a red-black tree enforces a weaker colour invariant and is what std::map, std::set and their multi variants use in every mainstream implementation. Both guarantee h = O(log n) and therefore O(log n) worst-case search, insert and delete. A plain BST has no rebalancing at all — if you write one and then feed it sorted data, nothing in the code will complain; performance will just quietly collapse. In production code, reach for std::map/std::set (ordered, O(log n), inorder iteration) or std::unordered_map/std::unordered_set (O(1) average, no order) and write your own BST only when you are learning or need custom augmentation.

Traversal space deserves a note: the Θ(n) time is unavoidable, but the O(h) auxiliary space is the recursion stack. For a balanced tree that is trivial; for a degenerate one it is O(n) stack frames and a real overflow risk. The iterative inorder shown earlier has the same O(h) bound but on the heap, where you can afford it.

// Why search costs one step per level, not one per node:
//
//        50          key = 65
//       /  \         65 > 50  -> discard {20,30,40} and 50 itself (4 nodes)
//     30    70       65 < 70  -> discard {80} and 70          (2 nodes)
//    / \   /  \      65 > 60  -> right of 60 is null -> absent
//  20  40 60   80
//
// Three comparisons for a 7-node tree. Each comparison halves the
// candidate set only if the tree is balanced -- that assumption is
// what turns O(h) into O(log n).

Rebuilding a tree from two traversals

The reverse problem: given traversal sequences, recover the tree. The rules, for a tree with distinct keys:

• inorder + preorder → unique tree. Yes.
• inorder + postorder → unique tree. Yes.
• preorder + postorder → not unique in general.
• inorder alone → not unique (it fixes left-to-right position but not depth).
• preorder alone → not unique for a general binary tree, but unique for a BST, because sorting the preorder recovers the inorder.

How inorder + preorder works. The first unconsumed preorder element is the root of the current subtree. Locate it in the inorder range: everything to its left is the left subtree, everything to its right is the right subtree, and the split also tells you the sizes. Recurse on the left first, because preorder emits the whole left subtree before the right one — so a single moving index p into the preorder array works if and only if you build left before right.

How inorder + postorder works. Same idea mirrored: consume postorder from the end, and build the right subtree first, because postorder emits left, then right, then root — read backwards that is root, right, left.

Why preorder + postorder fails. Consider a node with exactly one child. Preorder gives parent, child; postorder gives child, parent. Both are identical whether the child hangs left or right — neither sequence encodes side. Concretely, preorder = A B C and postorder = C B A are produced by four different trees (A with B as a left or right child, and B with C as a left or right child). Inorder is the traversal that does encode side: everything before the root belongs on the left. That is exactly why every workable pair includes inorder.

The exception: if the tree is full (every node has 0 or 2 children), no node has one child, the ambiguity disappears, and preorder + postorder does determine the tree.

Complexity. Naively scanning the inorder array for each root is O(n) per node → O(n²) worst case on a degenerate tree. Precomputing a key → inorder index hash map makes each lookup O(1) and the whole reconstruction Θ(n) time, Θ(n) space. That map is also why the keys must be distinct: with duplicates, "where is the root in the inorder?" has no single answer and the reconstruction is genuinely ambiguous.

Both functions below were run on preorder = A B D E C F, inorder = D B E A F C, postorder = D E B F C A; each reproduced the third sequence exactly.

// inorder + preorder  ->  build LEFT first, walk preorder forwards.
Node* buildFromPreIn(const std::vector<int>& pre, const std::vector<int>& in) {
    std::unordered_map<int,int> pos;                 // key -> index in inorder
    for (int i = 0; i < static_cast<int>(in.size()); ++i) pos[in[i]] = i;

    int p = 0;                                       // cursor into pre
    std::function<Node*(int,int)> build = [&](int lo, int hi) -> Node* {
        if (lo > hi) return nullptr;
        int   key = pre[p++];
        Node* n   = new Node(key);
        int   m   = pos[key];                        // root's slot in inorder
        n->left  = build(lo, m - 1);                 // MUST come first
        n->right = build(m + 1, hi);
        return n;
    };
    return build(0, static_cast<int>(in.size()) - 1);
}

// inorder + postorder ->  build RIGHT first, walk postorder backwards.
Node* buildFromPostIn(const std::vector<int>& post, const std::vector<int>& in) {
    std::unordered_map<int,int> pos;
    for (int i = 0; i < static_cast<int>(in.size()); ++i) pos[in[i]] = i;

    int p = static_cast<int>(post.size()) - 1;       // cursor from the end
    std::function<Node*(int,int)> build = [&](int lo, int hi) -> Node* {
        if (lo > hi) return nullptr;
        int   key = post[p--];
        Node* n   = new Node(key);
        int   m   = pos[key];
        n->right = build(m + 1, hi);                 // MUST come first
        n->left  = build(lo, m - 1);
        return n;
    };
    return build(0, static_cast<int>(in.size()) - 1);
}

Mistakes people actually make

1. Freeing in the wrong order. Covered above, but it is the single most common tree crash: delete n then touching n->left. Build the habit that teardown is always postorder.

2. Forgetting to reassign the parent's pointer. Writing insert(root->left, key); instead of root->left = insert(root->left, key); compiles cleanly, allocates the node, and drops it on the floor — a silent leak plus a missing key. The return-the-subtree-root idiom only works if the caller stores the result.

3. Deleting the successor node directly. In case 3, delete succ; leaves the successor's parent with a dangling pointer and orphans the successor's right subtree. Recurse instead, as shown.

4. Violating the Rule of Three. A class holding a raw Node* gets a compiler-generated copy constructor that copies the pointer. Pass the tree to a function by value and both objects destroy the same nodes: double free, guaranteed. Either write copy constructor + copy assignment + destructor (the copy-and-swap version below is short and exception-safe), or delete the copy operations, or store children in std::unique_ptr<Node> and let the compiler handle destruction.

5. Testing the BST property locally. Checking only left->key < key < right->key at each node passes trees that are not BSTs. In the code below, 12 hangs off 5's right; every local comparison holds, but 12 > 10 sits in 10's left subtree. The naive check returns true; the correct range-based check returns false. The alternative correct test is "an inorder walk is strictly increasing".

6. Height off-by-one. Mixing the edge convention (empty = −1) with the node convention (empty = 0) inside one problem. Also: height of a single node is 0 under the edge convention, not 1.

7. Assuming a BST stays balanced. No plain BST rebalances. Insert sorted data and you get a chain. If a question says "worst case", the answer is O(n), not O(log n).

8. Off-by-one in a hand-rolled circular buffer for level-order. If you implement the BFS queue as a fixed array with head, tail and wraparound, full and empty both look like head == tail. Either keep a separate count, or leave one slot unused and test (tail + 1) % capacity == head. Sizing the array n when the queue can transiently hold up to the widest level plus one is another classic overflow. Just use std::queue unless the exercise forbids it.

9. Duplicate keys in reconstruction. The key → index map silently keeps only the last occurrence, and the rebuilt tree is wrong. Reconstruction from traversals assumes distinct keys.

10. Recursing left and right in the wrong order during reconstruction. With a single shared cursor into the preorder array, swapping the two build calls corrupts everything after the first branch. Same for building left-before-right in the postorder version.

// --- Rule of Three: copy-and-swap ---
class BST {
public:
    BST() = default;
    ~BST() { destroy(root_); }
    BST(const BST& other) : root_(clone(other.root_)) {}      // deep copy
    BST& operator=(BST other) { std::swap(root_, other.root_); return *this; }
    void add(int k) { root_ = insert(root_, k); }
    const Node* root() const { return root_; }
private:
    Node* root_ = nullptr;
};

// --- Local check: WRONG ---
bool looksLikeBST(const Node* n) {
    if (!n) return true;
    if (n->left  && n->left->key  >= n->key) return false;
    if (n->right && n->right->key <= n->key) return false;
    return looksLikeBST(n->left) && looksLikeBST(n->right);
}

// --- Range check: CORRECT ---
// lo / hi are the nearest ancestors bounding this subtree (null = unbounded).
bool isBST(const Node* n, const Node* lo, const Node* hi) {
    if (!n) return true;
    if (lo && n->key <= lo->key) return false;
    if (hi && n->key >= hi->key) return false;
    return isBST(n->left, lo, n) && isBST(n->right, n, hi);
}

//        10
//       /  \        12 is in 10's LEFT subtree but 12 > 10.
//      5    20      looksLikeBST -> true   (wrong)
//       \           isBST        -> false  (right)
//        12

Exercises with solutions

Work through each question before opening the solution below it.

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \     /
       4   7   13

            45
        /        \
      25          60
     /  \        /  \
   15    35    55    80
        /  \        /  \
      30    40    70    90

            55
        /        \
      35          60
     /  \           \
   30    40          80
                    /  \
                  70    90

 T1:  A        T2:  A        T3:  A        T4:  A
     /             /               \             \
    B             B                 B             B
   /               \               /               \
  C                 C             C                 C

Related pages