Skip to content

021 — Construct Binary Tree from Preorder and Inorder Traversal

Source

1. Problem in simple words

তোমাকে একই tree-র দুটো traversal দেওয়া আছে — একটা preorder (Node → Left → Right) আর একটা inorder (Left → Node → Right)। দুটো list-এ একই value-গুলো আছে, শুধু ক্রম আলাদা। তোমার কাজ: এই দুটো থেকে আসল binary tree-টা আবার বানানো (root node ফেরত দেওয়া)।

ধরে নাও tree-তে কোনো value-র পুনরাবৃত্তি নেই (LeetCode তাই বলে) — না হলে কোন value কোনটা সেটা আলাদা করা যেত না।

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]   →   এই tree বানাও:

        3
       / \
      9   20
         /  \
        15   7

2. Which basic idea does this inherit from?

দুটো ভিত্তি একসাথে। প্রথমত preorder-এর গঠন: তার একদম প্রথম element সবসময় বর্তমান subtree-র root। দ্বিতীয়ত inorder-এর split-ক্ষমতা: ওই root-কে inorder-এ খুঁজে পেলে তার বাঁ পাশের সব value = বাঁ subtree, ডান পাশের সব = ডান subtree। আর সেই root-কে দ্রুত খুঁজতে আমরা ../../05-hashing/-এর hash map (value → inorder index) ব্যবহার করি।

3. What is the hidden math or logic?

লুকানো logic একটা recursive split:

1) preorder-এর পরের value = বর্তমান subtree-র root
2) inorder-এ সেই root-এর index = mid
3) inorder[left..mid-1] = বাঁ subtree (আকার = mid - left)
   inorder[mid+1..right] = ডান subtree
4) preorder-এ root-এর ঠিক পরে বাঁ subtree-র সব value, তারপর ডানের সব
5) বাঁ আগে গড়ো (preorder বাঁ আগে খায়), তারপর ডান — recurse

মূল গণিত: preorder যে ক্রমে node "জন্ম" দেয় (root আগে, তারপর পুরো বাঁ, তারপর পুরো ডান), inorder সেই অনুসারে left/right-এ ভাগ করে দেয়।

4. Which data structure is needed?

তিনটে জিনিস: ইনপুট দুটো list (preorder, inorder), একটা hash map (value → inorder index, যাতে root খোঁজা O(1)), আর recursion call stack। আর একটা চলন্ত pointer pre_idx — preorder-এ আমরা কতদূর এগিয়েছি।

5. Why this data structure fits

প্রতিবার root খুঁজতে inorder পুরো scan করলে O(n²) হয়ে যায়। hash map value-কে সরাসরি inorder index-এ map করে দেয়, তাই root খোঁজা O(1) — এখানেই ../../05-hashing/-এর শিক্ষা কাজে লাগে। recursion tree-র self-similar গঠনে নিখুঁত খাপ খায়: প্রতিটা subtree আবার একই preorder-root + inorder-split নিয়মে গড়া যায়।

6. Real-life analogy

ভাবো একটা মিছিলের দুটো রিপোর্ট আছে। একটায় (preorder) লেখা "আগে নেতা, তারপর তাঁর পুরো বাঁ দল, তারপর পুরো ডান দল"। আরেকটায় (inorder) সবাই বাঁ-থেকে-ডান দাঁড়ানোর ক্রমে আছে — মাঝখানে নেতা। তুমি preorder থেকে জানো নেতা কে; inorder-এ নেতাকে খুঁজে পেলেই বুঝে যাও তাঁর বাঁ পাশে কারা, ডান পাশে কারা। প্রতিটা উপ-দলে আবার একই কৌশল।

7. Visual explanation

preorder প্রথমে 3 দেয় (root); inorder-এ 3-এর বাঁয়ে [9], ডানে [15,20,7]:

preorder: [3 | 9 | 20 15 7]        3 = root
inorder:  [9 | 3 | 15 20 7]        9 = বাঁ subtree, [15,20,7] = ডান subtree

           3
          / \
   বাঁ → 9   20 ←(পরের root, ডান অংশের preorder থেকে)
            /  \
           15   7

8. Example input and output

Input : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: tree → level-order [3,9,20,null,null,15,7]

Input : preorder = [1,2], inorder = [2,1]      -> tree: 1 with left child 2
Input : preorder = [1,2], inorder = [1,2]      -> tree: 1 with right child 2
Edge  : preorder = [], inorder = []            -> None (খালি tree)
Edge  : preorder = [42], inorder = [42]        -> একটামাত্র node 42

9. Brute force thinking

প্রথম সরল চিন্তা — hash map ছাড়া: প্রতিবার preorder-এর সামনের value নাও (root), তারপর সেটা inorder-এ linear scan করে খুঁজে index বের করো, বাঁ/ডান slice বানিয়ে recurse করো।

1) root = preorder[0] = 3
2) inorder-এ 3 খোঁজো (scan) → index 1
3) বাঁ inorder = [9], ডান inorder = [15,20,7]
4) দুই পাশে আবার একই কাজ (প্রতিবার scan + নতুন slice)

10. Why brute force is slow

দুটো খরচ জমে। (১) প্রতিটা node-এ inorder পুরো scan করা — n বার scan, প্রতিটা O(n) পর্যন্ত → O(n²)। (২) প্রতিবার preorder[1:], inorder[:mid] ইত্যাদি নতুন slice বানানো — extra memory আর copy। দুটোই সরানো যায়: scan-এর জায়গায় hash map (O(1) lookup), আর slice-এর জায়গায় index-range (lo, hi) পাস করা।

11. Key observation

মূল observation দুটো: (১) preorder-এর প্রথম element সবসময় বর্তমান subtree-র root। (২) inorder-এ সেই root তার বাঁ আর ডান subtree-কে দুই ভাগে কেটে দেয়। এই দুটো একসাথে মানে — প্রতিটা subtree-র জন্য আমরা ঠিক জানি কোন value-গুলো বাঁয়ে আর কোনগুলো ডানে যাবে।

12. Optimized intuition

একটা চলন্ত pre_idx রাখো (preorder-এ পরবর্তী root কোথায়)। একটা helper build(lo, hi) inorder-এর [lo, hi] অংশ গড়ে: preorder[pre_idx] থেকে root নাও, pre_idx এগোও, hash map থেকে root-এর inorder index mid পাও, তারপর আগে build(lo, mid-1) (বাঁ), তারপর build(mid+1, hi) (ডান)। বাঁ আগে কারণ preorder root-এর পরেই পুরো বাঁ subtree রাখে। পুরো tree একবার গড়া হয় → O(n)।

13. Thinking tweak

মোচড়: list slice করা বন্ধ করো — তার বদলে index range নিয়ে কাজ করো, আর preorder-এ একটা ভাগ করা pointer (pre_idx) রাখো যেটা একই ক্রমে এগোয়। আর সবচেয়ে জরুরি ক্রম: বাঁ subtree আগে গড়ো, কারণ preorder root-এর ঠিক পরেই বাঁ-এর সব value রাখে; ডান আগে গড়লে pre_idx ভুল value তুলে আনবে।

14. Step-by-step dry run

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7], idx = {9:0, 3:1, 15:2, 20:3, 7:4}:

  1. pre_idx=0, build(0,4): root = 3 (pre_idx→1), mid = idx[3] = 1। বাঁ = build(0,0), ডান = build(2,4)।
  2. build(0,0): root = 9 (pre_idx→2), mid = 0। বাঁ = build(0,-1) = None, ডান = build(1,0) = None → leaf 9।
  3. build(2,4): root = 20 (pre_idx→3), mid = idx[20] = 3। বাঁ = build(2,2), ডান = build(4,4)।
  4. build(2,2): root = 15 (pre_idx→4) → leaf 15। build(4,4): root = 7 (pre_idx→5) → leaf 7।
  5. গঠন: 3 → (9, 20), 20 → (15, 7)। ঠিক target tree।

15. Python solution

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def level_order(root):
    """tree → trailing-None-ছাঁটা level-order list (যাচাইয়ের জন্য)।"""
    if root is None:
        return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        q.append(node.left)
        q.append(node.right)
    while out and out[-1] is None:    # লেজের None ছেঁটে দাও
        out.pop()
    return out


def build_from_pre_in(preorder, inorder):
    idx = {val: i for i, val in enumerate(inorder)}   # value → inorder index
    pre_idx = 0

    def build(lo, hi):
        nonlocal pre_idx
        if lo > hi:                       # খালি range → কোনো node নেই
            return None
        root_val = preorder[pre_idx]      # preorder-এর পরের value = root
        pre_idx += 1
        node = TreeNode(root_val)
        mid = idx[root_val]               # inorder-এ root কোথায় (O(1))
        node.left = build(lo, mid - 1)    # বাঁ আগে (preorder বাঁ আগে রাখে)
        node.right = build(mid + 1, hi)   # তারপর ডান
        return node

    return build(0, len(inorder) - 1)


# ---- tests ----
t1 = build_from_pre_in([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
assert level_order(t1) == [3, 9, 20, None, None, 15, 7]
t2 = build_from_pre_in([1, 2], [2, 1])
assert level_order(t2) == [1, 2]            # 2 হলো বাঁ child
t3 = build_from_pre_in([1, 2], [1, 2])
assert level_order(t3) == [1, None, 2]      # 2 হলো ডান child
assert level_order(build_from_pre_in([], [])) == []        # খালি tree
assert level_order(build_from_pre_in([42], [42])) == [42]  # একক node
print("সব test pass!")

16. Line-by-line code explanation

  • idx = {val: i ...} — value → inorder index map; root-কে inorder-এ O(1)-তে খুঁজতে।
  • pre_idx = 0 — preorder-এ পরবর্তী root-এর pointer; nonlocal দিয়ে সব recursive call একই pointer ভাগ করে।
  • if lo > hi: return None — base case: inorder-এর খালি range মানে এই দিকে কোনো node নেই।
  • root_val = preorder[pre_idx]; pre_idx += 1 — বর্তমান subtree-র root নাও আর pointer এগোও।
  • mid = idx[root_val] — inorder-এ root-এর অবস্থান; বাঁ/ডান কোথায় ভাগ হবে তা ঠিক করে।
  • node.left = build(lo, mid - 1) — আগে বাঁ, কারণ preorder root-এর পরেই বাঁ subtree রাখে।
  • node.right = build(mid + 1, hi) — তারপর ডান; এই ক্রম না মানলে pre_idx ভুল value তুলবে।

17. Output walkthrough

build_from_pre_in([3,9,20,15,7], [9,3,15,20,7]) ওই ছবির tree বানায়; level_order [3,9,20,None,None,15,7] দেয় — assert pass। [1,2]/[2,1] দেয় বাঁ child 2 ([1,2]), [1,2]/[1,2] দেয় ডান child 2 ([1,None,2]), খালি দেয় [], একক node দেয় [42] — সব pass। শেষে print: সব test pass!।

18. Time complexity

O(n) — প্রতিটা node ঠিক একবার তৈরি হয়, আর hash map-এর কল্যাণে প্রতিটা root-lookup O(1)। map বানাতে শুরুতে O(n)। (linear-scan version হতো O(n²)।)

19. Space complexity

O(n) — hash map-এ n entry, plus recursion call stack tree-র height পর্যন্ত (skewed হলে O(n), balanced হলে O(log n))। output tree নিজেও O(n), যা অনিবার্য।

20. Common mistakes

  • ডান subtree আগে গড়া — pre_idx যেহেতু ভাগ করা ও preorder বাঁ আগে রাখে, ডান আগে গড়লে value-গুলো এলোমেলো হয়ে যাবে।
  • প্রতিবার list slice করা (preorder[1:]) — কাজ করে কিন্তু O(n²) আর বাড়তি memory; index-range পাস করাই ভালো।
  • inorder index খুঁজতে প্রতিবার inorder.index(root) ডাকা — সেটাই O(n²) করে দেয়; hash map লাগবে।
  • duplicate value থাকলে এই পদ্ধতি ভাঙে — কোন copy কোনটা তা inorder-এ অদ্বিতীয়ভাবে বলা যায় না (problem তাই unique ধরে)।

21. Which basic problem this inherits from

ভিত্তি: traversal-patterns.md-র preorder/inorder সংজ্ঞা (preorder root আগে দেয়, inorder root-এ মাঝে থাকে) আর ../../05-hashing/-এর value→index map। দুটো এক হলে — "preorder থেকে root, inorder থেকে split" — পুরো construction দাঁড়িয়ে যায়।

22. Similar harder problems

23. Pattern learned

Traversal-driven construction: একটা traversal থেকে root চিনে নাও (preorder-এর প্রথম / postorder-এর শেষ), আরেকটা (inorder) দিয়ে বাঁ-ডান ভাগ করো; hash map দিয়ে split O(1) করো আর index-range-এ recurse করো। দুই traversal থেকে tree গড়ার সব problem-এর কঙ্কাল এটাই।

24. Final summary

ভবিষ্যতের আমাকে: "preorder = root আগে, inorder = বাঁ-ডান ভাগ করে; hash map দিয়ে split খোঁজো, বাঁ আগে গড়ো।" ভাগ করা pre_idx আর সঠিক বাঁ-আগে ক্রম — এই দুটোই মূল। 'দুটো traversal থেকে tree বানাও' টাইপ problem দেখলেই এই construction চালটা মনে করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।