Construct Tree from Inorder & Preorder

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Preorder[0] is root. Find it in inorder to split left and right subtrees. Recurse.

Algorithm

1Root = preorder[0]. Index in inorder = k. Left subtree size = k.
2Recurse: left = (preorder[1..k], inorder[0..k-1]). Right = (preorder[k+1..], inorder[k+1..]).

Common Pitfalls

•Use a hash map for O(1) inorder lookups. Pass index ranges instead of slices.

Construct Tree from Inorder & Preorder.java

Java

// Approach: Recursively build: preorder[0] is root, find it in inorder to split left/right subtrees.
// Use a HashMap for O(1) inorder lookup.
// Time: O(n) Space: O(n)
class Node {
    int data;
    Node left, right;

    Node(int key) {
        data = key;
        left = right = null;
    }
}

class Solution {
    public static Node buildTree(int inorder[], int preorder[]) {
        int n = inorder.length;
        Node root = construct(inorder, 0, n - 1, preorder, 0, n - 1);
        return root;
    }

    public static Node construct(int[] in, int isi, int iei, int[] pre, int psi, int pei) {
        if (isi > iei || psi > pei)
            return null;

        Node node = new Node(pre[psi]);

        int cnt = 0;
        int itr = isi;

        while (in[itr] != node.data) {
            cnt++;
            itr++;
        }

        Node left = construct(in, isi, itr - 1, pre, psi + 1, psi + cnt);
        Node right = construct(in, itr + 1, iei, pre, psi + cnt + 1, pei);

        node.left = left;
        node.right = right;

        return node;
    }
}

Was this solution helpful?