Tree Traversals Interview Questions

February 26, 2026 • By Surya Singh • DSA • Trees • BFS • DFS • Interview

Tree traversal interview questions — inorder, preorder, postorder, BFS, DFS patterns.

DSATreesBFSDFSInterview

Key Takeaways

  • 1Four main traversals: inorder (left-root-right), preorder (root-left-right), postorder (left-right-root), level-order (BFS).
  • 2Inorder on a BST gives sorted order; preorder helps reconstruct the tree with known structure.
  • 3Recursive is simple; iterative uses an explicit stack (or queue for BFS) to avoid stack overflow.
  • 4Morris traversal can do inorder in O(1) space by threading the tree with successor pointers.

The questions below are commonly asked in technical interviews. Each answer is written to help you understand the concept clearly and explain it confidently. Focus on understanding the "why" behind each answer—that is what interviewers care about.

In this guide

Interview Questions & Answers

What is the difference between inorder, preorder, and postorder traversal?

The names refer to when you "visit" the root relative to the children. Inorder: left subtree first, then root, then right. Preorder: root first, then left, then right. Postorder: left, then right, then root. For a binary search tree, inorder visits nodes in sorted order—that is why it is used for "validate BST" or "kth smallest element." Preorder is useful for copying a tree or serialization where you need the root first. Postorder is used when you need children processed before the parent (e.g., deleting a tree, or when the root depends on subtree results).

void Inorder(TreeNode? n, List<int> acc) {
    if (n == null) return;
    Inorder(n.left, acc);
    acc.Add(n.val);
    Inorder(n.right, acc);
}
void Preorder(TreeNode? n, List<int> acc) {
    if (n == null) return;
    acc.Add(n.val);
    Preorder(n.left, acc);
    Preorder(n.right, acc);
}
void Postorder(TreeNode? n, List<int> acc) {
    if (n == null) return;
    Postorder(n.left, acc);
    Postorder(n.right, acc);
    acc.Add(n.val);
}

When would I use iterative instead of recursive tree traversal?

Use iterative when the tree is very deep and recursive calls could cause a stack overflow, or when an interviewer asks for an iterative solution. Iterative DFS uses an explicit stack: push the root, then loop—pop, visit, push right then left (so left is processed first). For BFS (level-order), use a queue: enqueue root, then loop—dequeue, visit, enqueue left then right. Iterative solutions also make it easier to pause and resume (e.g., for generators or streams) because you control the stack explicitly.

// Iterative inorder using stack
List<int> InorderIter(TreeNode? root) {
    var result = new List<int>();
    var stack = new Stack<TreeNode>();
    var curr = root;
    while (curr != null || stack.Count > 0) {
        while (curr != null) {
            stack.Push(curr);
            curr = curr.left;
        }
        curr = stack.Pop();
        result.Add(curr.val);
        curr = curr.right;
    }
    return result;
}

How do I do level-order (BFS) traversal and when is it useful?

Level-order visits nodes level by level: first the root, then all nodes at depth 1, then depth 2, and so on. Use a queue: enqueue the root. While the queue is not empty, dequeue a node, visit it, enqueue its left and right children (if they exist). Useful for finding the minimum depth of a tree, printing level by level, or when you need to process nodes in "waves" (e.g., right-side view of a tree—take the last node of each level). Time O(n), space O(w) where w is the maximum width of the tree.

List<int> LevelOrder(TreeNode? root) {
    var result = new List<int>();
    if (root == null) return result;
    var q = new Queue<TreeNode>();
    q.Enqueue(root);
    while (q.Count > 0) {
        var node = q.Dequeue();
        result.Add(node.val);
        if (node.left != null) q.Enqueue(node.left);
        if (node.right != null) q.Enqueue(node.right);
    }
    return result;
}

What is Morris traversal and when would I use it?

Morris traversal does inorder in O(n) time and O(1) space—no recursion and no explicit stack. It works by temporarily threading the tree: for each node without a left child, visit it and go right. If it has a left child, find its inorder predecessor (rightmost node in the left subtree), make the predecessor's right pointer point to the current node (creating a thread), then go left. When you later reach the current node via the thread, you remove the thread and go right. Use it when O(1) space is required; otherwise recursive or iterative with a stack is simpler.

How do I reconstruct a binary tree from preorder and inorder traversals?

The first element of preorder is the root. Find that root in inorder—everything left of it is the left subtree, everything right is the right subtree. Recursively build the left subtree from the left portion of inorder and the next elements in preorder; build the right subtree from the right portion and the remaining preorder elements. For efficiency, use a hash map to find the root index in inorder in O(1). The same idea works for postorder + inorder (root is the last element of postorder). Preorder + postorder does not uniquely define a tree for all cases.

TreeNode? BuildTree(int[] preorder, int[] inorder) {
    var inIdx = new Dictionary<int, int>();
    for (int i = 0; i < inorder.Length; i++) inIdx[inorder[i]] = i;
    int pre = 0;
    return Build(0, inorder.Length - 1);
    TreeNode? Build(int lo, int hi) {
        if (lo > hi) return null;
        var root = new TreeNode(preorder[pre++]);
        int mid = inIdx[root.val];
        root.left = Build(lo, mid - 1);
        root.right = Build(mid + 1, hi);
        return root;
    }
}

Loading...

XLinkedInFacebook
Surya Singh

Surya Singh

Azure Solutions Architect & AI Engineer

Microsoft-certified Azure Solutions Architect with 8+ years in enterprise software, cloud architecture, and AI/ML deployment. I build production AI systems and write about what actually works—based on shipping code, not theory.

  • Microsoft Certified: Azure Solutions Architect Expert
  • Built 20+ production AI/ML pipelines on Azure
  • 8+ years in .NET, C#, and cloud-native architecture
LinkedInTwitter/XAbout Me