Skip to content

003 — Binary Tree Preorder Traversal

Source

  • Original source: Classic tree traversal exercise
  • Platform: LeetCode — https://leetcode.com/problems/binary-tree-preorder-traversal/
  • Topic: trees
  • Difficulty: Easy
  • Pattern: Traversal order
  • Basic idea inherited from: Inorder, visit-মুহূর্ত সরানো — value নেওয়ার লাইন একদম উপরে তুলে দাও

1. Problem in simple words

তোমাকে একটা binary tree-র root দেওয়া আছে। সব value একটা list-এ ফেরত দাও — preorder ক্রমে, মানে Node → Left → Right।

প্রতিটা node-এ: আগে নিজের value নাও, তারপর পুরো বাঁ-দিক, তারপর পুরো ডান-দিক। parent সবসময় তার সব descendant-এর আগে আসে।

1
 \
  2
 /
3        ← preorder = [1, 2, 3]

2. Which basic idea does this inherit from?

এটা inorder-এরই যমজ ভাই (এই tracker-এর #2)। একই recursion কঙ্কাল, শুধু value নেওয়ার লাইনটা মাঝখান থেকে একদম উপরে তুলে দেওয়া হয়েছে — তাই node তার child-দের আগে visit হয়। "visit-মুহূর্ত সরানো" — এটাই তিন DFS traversal-এর মধ্যে পার্থক্য।

3. What is the hidden math or logic?

লুকানো logic আবার একটা ক্রমের সংজ্ঞা:

preorder(empty) = []
preorder(node)  = [node.val] + preorder(node.left) + preorder(node.right)

এর একটা গুরুত্বপূর্ণ ধর্ম: parent সবসময় আগে লেখা হয় বলে preorder output থেকে tree-টা top-down আবার বানানো যায়। এজন্যই preorder হলো copy / serialize-এর স্বাভাবিক ক্রম (traversal-patterns.md দেখো)।

4. Which data structure is needed?

একটা output list আর recursion call stack। recursion-এর বদলে চাইলে একটা explicit stack (../../04-stack-and-queue/) — root push করো, pop করে visit করো, তারপর RIGHT তারপর LEFT push করো (যাতে left আগে pop হয়)।

5. Why this data structure fits

Tree self-similar, তাই recursion প্রতিটা subtree আলাদা সামলায়। preorder-এ আমরা node-এ পৌঁছেই (on ARRIVAL) value নিই, তাই কোনো জিনিস "মনে রেখে পরে নেওয়ার" ঝামেলা নেই — পৌঁছালাম, লিখলাম, নিচে নামলাম। stack/recursion শুধু "এরপর কোন দিক বাকি" ধরে রাখে।

6. Real-life analogy

একটা বইয়ের table of contents ভাবো। আগে chapter-এর শিরোনাম লেখা হয়, তারপর তার সব section, তারপর পরের chapter। তুমি একটা heading-এ পৌঁছেই সেটা লিখে ফেলো, তারপর তার ভেতরে ঢোকো। এটাই preorder — "আগে আমি, তারপর আমার ভেতরের সব।"

7. Visual explanation

★ মানে value নেওয়া হলো — preorder-এ সেটা node-এ পৌঁছানোমাত্রই (নিচে নামার আগে):

        1★
       / \
      2★  3★
     / \
    4★  5★

হাঁটা: 1★ (পৌঁছেই) → 2★ → 4★ → 5★ → 3★
preorder = [1, 2, 4, 5, 3]

8. Example input and output

Input : root = [1,null,2,3]
Output: [1, 2, 3]

Input : root = []        -> Output: []     (খালি tree)
Input : root = [1]       -> Output: [1]    (একটা node)

9. Brute force thinking

Traversal নিজেই কাজ, তাই brute force বলতে iterative explicit-stack version — recursion ছাড়া হাতে stack চালানো।

1) root-কে stack-এ push করো
2) stack থেকে pop করো → value নাও
3) আগে RIGHT, তারপর LEFT push করো (যাতে left আগে pop হয়)
4) stack খালি না হওয়া পর্যন্ত ধাপ 2 চালাও

10. Why brute force is slow

Iterative version-ও O(n), slow না — কিন্তু "right তারপর left push" উল্টো বোধ হয়, ভুল হওয়া সহজ। recursion সেই subtlety নিজেই সামলায়, code পরিষ্কার থাকে। iterative লাগে শুধু খুব গভীর tree-তে Python-এর recursion limit এড়াতে।

11. Key observation

মূল observation: inorder-এর তুলনায় শুধু একটা লাইন উপরে উঠেছে — append এখন দুই recursive call-এর আগে। তাই node তার বংশধরদের আগে লেখা হয়। ক্রম বদলানো মানে শুধু এই এক লাইন সরানো।

12. Optimized intuition

তিন লাইনের recursion: এই node-এর value append করো, বাঁয়ে নামো, ডানে নামো। None-এ চুপচাপ ফিরে যাও। একবার tree ঘোরা — প্রতিটা node পৌঁছানোমাত্র লেখা হয়।

13. Thinking tweak

মোচড়: "preorder মানে কী" আলাদা করে মুখস্থ না করে ভাবো — "inorder-এর append লাইনটা টেনে একদম উপরে তুলে দিলাম।" তিন traversal = একটাই কঙ্কাল, append-লাইনের তিনটা অবস্থান (উপরে / মাঝে / নিচে)।

14. Step-by-step dry run

Input [1,null,2,3] (tree: 1-এর right 2, 2-এর left 3):

  1. visit(1): পৌঁছেই append 1। out = [1]।
  2. visit(1.left = None): চুপচাপ ফিরল।
  3. visit(1.right = 2): append 2। out = [1, 2]।
  4. visit(2.left = 3): append 3। out = [1, 2, 3]। left/right None → ফিরল।
  5. সব শেষ → [1, 2, 3]।

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 build_tree(values):
    """level-order list (None = missing child) থেকে tree বানায়।"""
    if not values:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


def preorder_traversal(root):
    out = []

    def visit(node):
        if node is None:        # base case: খালি subtree
            return
        out.append(node.val)    # 1) পৌঁছেই নিজের value (on ARRIVAL)
        visit(node.left)        # 2) তারপর পুরো বাঁ-দিক
        visit(node.right)       # 3) তারপর পুরো ডান-দিক

    visit(root)
    return out


# ---- tests ----
assert preorder_traversal(build_tree([1, None, 2, 3])) == [1, 2, 3]
assert preorder_traversal(build_tree([])) == []
assert preorder_traversal(build_tree([1])) == [1]
assert preorder_traversal(build_tree([1, 2, 3, 4, 5])) == [1, 2, 4, 5, 3]
print("সব test pass!")

16. Line-by-line code explanation

  • out = [] — value জমানোর জায়গা।
  • if node is None: return — base case; খালি subtree থেকে কিছু যোগ হয় না।
  • out.append(node.val) — মূল চাল: node-এ পৌঁছেই, নিচে নামার আগে value নাও।
  • visit(node.left) / visit(node.right) — তারপর বাঁ, তারপর ডান।
  • return out — পুরো preorder sequence।

17. Output walkthrough

[1,null,2,3] → [1, 2, 3] (dry run-এর সাথে মেলে)। খালি tree → []; একক node → [1]; [1,2,3,4,5] → [1,2,4,5,3] (ছবির সাথে মেলে)। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(n) — প্রতিটা node ঠিক একবার visit ও append।

19. Space complexity

O(n) output list-এর জন্য; recursion stack আলাদাভাবে O(h) (balanced-এ O(log n), chain-এ O(n))।

20. Common mistakes

  • append লাইন নিচে রেখে ভুল করে inorder/postorder বানিয়ে ফেলা।
  • iterative version-এ left আর right push-এর ক্রম উল্টে দেওয়া (right আগে push করতে হয়)।
  • base case বাদ দিয়ে None ছোঁয়া।

21. Which basic problem this inherits from

ভিত্তি: Inorder Traversal (#2) — একই কঙ্কাল, append-লাইন উপরে তোলা। সাথে traversal-patterns.md-র preorder sketch, যেখানে দেখানো হয় কেন preorder = copy/serialize-এর ক্রম।

22. Similar harder problems

23. Pattern learned

DFS visit-order — arrival version: value নাও node-এ পৌঁছানোমাত্র, তাই parent আগে। এই top-down ধর্মই tree clone, serialize, আর "decision উপর থেকে নিচে পাঠানো" সব problem-এর ভিত্তি।

24. Final summary

ভবিষ্যতের আমাকে: "preorder = Node, Left, Right — পৌঁছেই value নাও, parent আগে।" copy বা serialize-এর কথা শুনলেই preorder মনে করবে। আর তিন traversal গুলিয়ে গেলে মনে রেখো: একটাই কঙ্কাল, append-লাইনের অবস্থানই সব।

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