Lesson 1 � Beginner

Binary Tree: Structure aur Traversals

Binary Tree DSA ki sabse powerful data structure hai. Arrays, linked lists ke baad trees ka number hai � ye hierarchical data represent karte hain aur interview mein har doosre question mein aate hain. Chalo step by step samajhte hain.

? 24 min✓ Beginner✓ Recursion basics

Binary Tree hota kya hai?

WHAT

Binary Tree ek non-linear data structure hai jismein har node maximum 2 children rakh sakta hai � left child aur right child. Ye ek hierarchical structure hai jismein ek root node hota hai aur baaki nodes uske neeche arranged hote hain.

WHEN

Jab data naturally hierarchical ho � jaise file system (folders inside folders), organization chart, ya DOM tree. Jab search operations fast chahiye (BST), jab sorting ya searching ke liye tree-based structures use karo.

WHERE

Har jagah! File systems, databases (B-trees), compilers (AST), maps, priority queues. Interview mein trees se 30%+ questions aate hain � traversals, LCA, construction, serialization sab covered hoga.

Mental Model: Imagine karo ek family tree � top pe grandfather hai (root), uske neeche 2 bacche (left aur right children), unke neeche aur bacche. Binary tree mein har node maximum 2 children rakh sakta hai. Ye simple rule hai jo tree ko efficient banata hai.

# Python mein Binary Tree ka Node structure
class Node:
 def __init__(self, val):
 self.val = val
 self.left = None # Left child
 self.right = None # Right child

# Tree banana
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

# Ye tree ye banega:
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7

Har node mein 3 cheezein hoti hain � value (data), left pointer (left child ki taraf), aur right pointer (right child ki taraf). Agar koi child nahi hai toh pointer None hoga.

Important Terms

Trees ke liye kuch special terms hain jo interview mein bar bar aate hain. Inhe yaad rakhna zaroori hai:

# 1 ✓ Root (sabse upar ka node)
# / \
# 2 3 ✓ Internal nodes (children hain)
# / \ / \
# 4 5 6 7 ✓ Leaf nodes (koi child nahi)

# Height of tree = 2 (root se longest path)
# Depth of node 5 = 2 (root se 5 tak edges)
# Level of node 3 = 1 (root level 0 se start)

Root

Tree ka sabse pehla node � jiska koi parent nahi hota. Binary tree mein sirf ek root hota hai.

Leaf Node

Wo node jiske koi bhi children na ho � left aur right dono None ho. End nodes leaves kehlate hain.

Internal Node

Wo node jiske kam se kam ek child ho. Root bhi internal node ho sakta hai agar uske children hon.

Key Point: Height = root se longest path (edges mein). Depth = kisi node se root tak ka distance. Root ki depth 0 hoti hai. Height aur depth dono edges count karte hain, nodes nahi.

Tree Traversals

Traversal ka matlab hai har node ko ek ek karke visit karna. Arrays mein linear traversal hota hai (0, 1, 2...), but trees mein 3 main traversal orders hain � Inorder, Preorder, Postorder. Ye recursion se implement hote hain.

# Inorder Traversal: LEFT ✓ ROOT ✓ RIGHT
def inorder(node):
 if node is None:
 return
 inorder(node.left) # Pehle left subtree
 print(node.val) # Phir root
 inorder(node.right) # Phir right subtree

# Preorder Traversal: ROOT ✓ LEFT ✓ RIGHT
def preorder(node):
 if node is None:
 return
 print(node.val) # Pehle root
 preorder(node.left) # Phir left subtree
 preorder(node.right) # Phir right subtree

# Postorder Traversal: LEFT ✓ RIGHT ✓ ROOT
def postorder(node):
 if node is None:
 return
 postorder(node.left) # Pehle left subtree
 postorder(node.right) # Phir right subtree
 print(node.val) # Last mein root

Ye 3 traversals recursion ke basic example hain. Har function ek base case check karta hai (agar node None hai toh return), phir left jaata hai, kaam karta hai, phir right jaata hai. Bas order alag hai!

Inorder Special Property: Agar tree BST hai (Binary Search Tree), toh inorder traversal sorted order mein values deta hai. Ye property bahut kaam aati hai � sorted check karne ke liye inorder nikalo aur dekho ki sorted hai ya nahi.

Traversal ka Visual Example

Is tree ko dekho aur har traversal ka output samjho:

# 1
# / \
# 2 3
# / \
# 4 5

# Inorder: 4 ? 2 ? 5 ? 1 ? 3
# (Left, Root, Right � leftmost se shuru)

# Preorder: 1 ? 2 ? 4 ? 5 ? 3
# (Root, Left, Right � root pehle)

# Postorder: 4 ? 5 ? 2 ? 3 ? 1
# (Left, Right, Root � root last mein)

# Verify karo khud se!
tree = Node(1)
tree.left = Node(2)
tree.right = Node(3)
tree.left.left = Node(4)
tree.left.right = Node(5)

Mnemonic Yaad Rakho: Inorder = In between (Left ke baad, Right se pehle). Preorder = Previously (pehle root). Postorder = Post (baad mein root). Simple hai na?

Try it: code khud likho

Exercise

Question: Given tree [1, 2, 3, 4, 5] (root=1, left=2, right=3, left.left=4, left.right=5), inorder traversal ka output kya hoga✓ Answer mein space-separated numbers daalo.

Question: Same tree [1, 2, 3, 4, 5] ka preorder traversal kya hoga✓ Answer mein space-separated numbers daalo.

Common mistakes

Base case bhoolna: Recursive traversal mein agar if node is None: return nahi likha toh infinite recursion hoga aur stack overflow ho jayega.
Traversal order confuse karna: Inorder mein root beech mein hai, Preorder mein pehle hai, Postorder mein last mein hai. Yaad rakhne ka tarika: LNR (In), NLR (Pre), LRN (Post).
Nodes vs Edges: Height aur depth edges count karte hain, nodes nahi. 3-node tree ki height 2 hai, 3 nahi.
Leaf node ka left/right access karna: Leaf node ke left aur right None hote hain. Unpe koi operation karne se error aayega.

Lesson complete?

Binary Tree basics samajh aa gaye✓ Ab BST (Binary Search Tree) seekhte hain � jo search operations ko O(log n) fast banata hai.