Construct Binary Tree from Preorder and Inorder Traversal

Medium · Trees · Explanation and code example

Morris Traversal

How it works

Morris traversal allows us to build the tree iteratively without using a recursion stack. The idea is to use the right pointers of nodes to temporarily store parent references, simulating the call stack. We build nodes as we iterate through preorder, connecting them via left/right pointers. When we finish a left subtree (detected by matching the inorder sequence), we restore the original structure by clearing temporary links and moving up the tree.

Steps

  1. Create a dummy head node and set curr to point to it.
  2. Iterate through preorder with index i and inorder with index j.
  3. Create a new node for preorder[i] and attach it as curr's right child, then move curr to this new node.
  4. While preorder[i] does not match inorder[j], keep creating left children (storing parent in right pointer).
  5. When a match is found, increment j. While curr.right exists and matches inorder[j], clear the temporary right link and move up.
  6. Continue until all nodes are processed.
  7. Return head.right as the actual root.

Complexity

  • Time complexity: O(n)
  • Space complexity:
    • O(1) extra space.
    • O(n) for the output tree.

Things to watch for

Off-by-One Error When Splitting Arrays

The split point mid represents the root's index in inorder. When slicing preorder, the left subtree uses preorder[1:mid+1] (not preorder[1:mid]), since there are exactly mid elements in the left subtree.

Building Right Subtree Before Left Subtree

When using a global preorder index, the left subtree must be built first. Preorder visits root, then left, then right. Building right first consumes wrong nodes from the preorder array.

Confusing Preorder and Inorder Roles

The root always comes from preorder (first element), while the split point is found in inorder. Swapping these roles produces an incorrect tree structure.

Python code example

from typing import List, Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        head = TreeNode(None)
        curr = head
        i, j, n = 0, 0, len(preorder)
        while i < n and j < n:
            # Go right and then as far left as possible
            curr.right = TreeNode(preorder[i], right = curr.right)
            curr = curr.right
            i += 1
            while i < n and curr.val != inorder[j]:
                curr.left = TreeNode(preorder[i], right=curr)
                curr = curr.left
                i += 1
            j += 1
            while curr.right and j < n and curr.right.val == inorder[j]:
                prev = curr.right
                curr.right = None
                curr = prev
                j += 1

        return head.right

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* head = new TreeNode(0);
        TreeNode* curr = head;
        int i = 0, j = 0, n = preorder.size();

        while (i < n && j < n) {
            curr->right = new TreeNode(preorder[i], nullptr, curr->right);
            curr = curr->right;
            i++;
            while (i < n && curr->val != inorder[j]) {
                curr->left = new TreeNode(preorder[i], nullptr, curr);
                curr = curr->left;
                i++;
            }
            j++;
            while (curr->right && j < n && curr->right->val == inorder[j]) {
                TreeNode* prev = curr->right;
                curr->right = nullptr;
                curr = prev;
                j++;
            }
        }
        return head->right;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations