Binary tree — structure, traversals - preorder, inorder, postorder (recursive and iterative)

3.4.2 · Coding › Trees

Binary tree KYA hota hai?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None   # left subtree (a Node or None)
        self.right = None  # right subtree

DO children kyun? "Binary" = base-2 branching. Yahi restriction hai jo hume cleanly reason karne deti hai: har node par exactly do recursive sub-problems hote hain (left subtree, right subtree), aur dono khud ek binary tree hote hain. Yahi self-similarity hai jis wajah se recursion trees par perfectly fit hoti hai.

Teeno traversals ke peeche EK hi idea

Ek traversal har node ko exactly ek baar visit karta hai. Har node ke liye aap 3 kaam karte ho:

1. N — current Node ko process (visit) karo.
2. L — Left subtree mein recurse karo.
3. R — Right subtree mein recurse karo.

L hamesha R se pehle aata hai. Sirf yahi fark hai ki N kahan baithta hai:

Recursive traversals (first principles se derive karo)

Recursion hi definition hai. "Ek tree traverse karna = root visit karna + left traverse karna + right traverse karna", bas teeno lines ka order badal do:

def preorder(node, out):
    if node is None: return        # base case: empty tree → kuch nahi
    out.append(node.val)           # N
    preorder(node.left, out)       # L
    preorder(node.right, out)      # R
 
def inorder(node, out):
    if node is None: return
    inorder(node.left, out)        # L
    out.append(node.val)           # N
    inorder(node.right, out)       # R
 
def postorder(node, out):
    if node is None: return
    postorder(node.left, out)      # L
    postorder(node.right, out)     # R
    out.append(node.val)           # N

if node is None: return kyun? Yeh empty tree ka base case hai. Iske bina recursion kabhi rukti nahi aur aap None.left par crash kar jaate ho.

Iterative traversals (WHY: recursion = ek stack hai)

Iterative Preorder

Idea: ek node pop karo, use visit karo, pehle right push karo phir left (taaki left pehle pop ho — hume N L R chahiye).

def preorder_iter(root):
    if root is None: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)          # N — pop par visit
        if node.right: stack.append(node.right)  # R pehle push karo…
        if node.left:  stack.append(node.left)   # …taaki L pehle pop ho
    return out

Right ko left se pehle kyun push karo? Stack order reverse karta hai. Left ko pehle process karne ke liye left ko last push karna padta hai (top par).

Iterative Inorder

Idea: jitna ho sake left jaate raho aur nodes push karte raho, phir pop karo (visit karo), phir right ki taraf mudo.

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                # 1) left mein ghuso, ancestors stack karte jao
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()         # 2) sabse leftmost unvisited node
        out.append(cur.val)       # N — L aur R ke beech visit karo
        cur = cur.right           # 3) ab uski right subtree handle karo
    return out

Pehle left mein kyun ghuste hain? Inorder ko left subtree poori khatam chahiye node se pehle, isliye ancestors ko stash karte hain aur visit sirf wapas aate waqt karte hain.

Iterative Postorder (two-stack trick — yaad rakhne mein sabse aasaan)

Idea: Postorder "Root Right Left" ka reverse hai. Preorder jaisa pass karo lekin left ko right se pehle push karo, ek doosri stack mein collect karo, phir reverse karo.

def postorder_iter(root):
    if root is None: return []
    s1, s2 = [root], []
    while s1:
        node = s1.pop()
        s2.append(node.val)         # Root,Right,Left order bana rahe hain
        if node.left:  s1.append(node.left)
        if node.right: s1.append(node.right)
    return s2[::-1]                 # reverse → Left,Right,Root = postorder

Reverse karna kyun kaam karta hai? N R L ko reverse karo toh L R N milta hai, jo exactly postorder hai. Kaafi smart trick hai yeh.

Complexity (derive karo)

• Time = $O(n)$ saari traversals ke liye: $n$ nodes mein se har ek ko constant baar visit (push/pop) kiya jaata hai.
• Space = $O(h)$ jahan $h$ = tree height (stack/recursion depth).
  • Balanced tree: $h\approx {\log }_{2}n$ → $O(\log n)$.
  • Skewed (linked-list jaisi) tree: $h=n$ → $O(n)$.

$O(n)$ nahi balki $O(h)$ space kyun? Kisi bhi moment par stack mein sirf root se current node tak ka ancestor chain hota hai — har level par at most ek.

Flashcards

Connections

• Binary Search Tree — inorder yahan sorted order deta hai.
• Recursion and the Call Stack — batata hai kyun DFS ⇔ stack hai.
• Stack (LIFO) — iterative traversals ka engine.
• Tree Height and Balance — $O(h)$ space ko drive karta hai.
• Level-order Traversal (BFS) — in DFS orders ka queue-based cousin.
• Construct Tree from Preorder + Inorder — traversal uniqueness ka application.

Concept Map