Tree traversals

Three DFS orders: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root). Level order uses BFS queue—layer by layer.

When each matters

• Inorder on BST → sorted values
• Preorder → copy/serialize tree
• Postorder → delete tree bottom-up
• Level order → shortest depth per node in unweighted tree

Recursive inorder

#include 

struct Node { int v; Node* L; Node* R; };

void inorder(Node* n) {
    if (!n) return;
    inorder(n->L);
    std::cout << n->v << " ";
    inorder(n->R);
}

int main() {
    Node a{2, nullptr, nullptr}, b{1, nullptr, nullptr}, c{3, nullptr, nullptr};
    a.L = &b; a.R = &c;
    inorder(&a);
    std::cout << "\n";
    return 0;
}

Complexity

Visit each node once → O(n) time, O(h) recursion stack for height h.

Important interview questions and answers

1. Q: Inorder output on BST?
   A: Ascending sorted order if BST property holds.
2. Q: Iterative traversal?
   A: Use explicit stack to simulate recursion—same O(n) time.

Self-check

1. Write inorder visit order for root 10, left 5, right 15.
2. What is traversal time for n nodes?

Tip: Inorder on valid BST prints sorted values—memorize that interview fact.