TREE TRAVERSAL Definition

Tree ek non-linear data structure (गैर-रेखीय डेटा संरचना) hota hai jismein data hierarchical (पदानुक्रमित) tareeke se store hota hai.

• Tree mein sabse upar wala node Root kehlata hai (jaise aapke image mein 30).
• Har node ke paas zero ya zero se zyada Child nodes ho sakte hain.
• Jo nodes kisi aur node se judte hain, woh Parent node kehte hain.
• Jin nodes ke koi child nahi hote, woh Leaf nodes kehlati hain (jaise: 5, 18, 25, 35, 45, 60).

Aapke dwara di gayi image ek Binary Search Tree (BST) hai, jismein:

1. Har node ke maximum do child ho sakte hain.
2. Left child ki value parent se kam hoti hai.
3. Right child ki value parent se zyada hoti hai.

Tree Traversal Kya Hota Hai?

Tree Traversal ka matlab hai tree ke har node ko ek baar visit karna. Traversal ke alag-alag tareeke hote hain, jisse hum nodes ko ek specific order mein process kar sakte hain.

Binary Tree ko traverse karne ke teen main tareeke hain: In-order, Pre-order, aur Post-order. Ye teeno tareeke Depth First Search (DFS) ke prakar hain.

1️⃣ Pre-order Traversal (पहले ऑर्डर)

Definition:
Pre-order traversal mein, hum pehle Root node ko visit karte hain, phir Left Subtree ko traverse karte hain, aur aakhir mein Right Subtree ko traverse karte hain.

• Order: Root → Left → Right

Algorithm:

1. Visit the Root node. (Print the data)
2. Recursively call Pre-order on the Left subtree.
3. Recursively call Pre-order on the Right subtree.

Aapke Example Tree Par:

• Root: 30
• Left Subtree (Root 20): 20 → 15 → 5 → 18 → 25
• Right Subtree (Root 40): 40 → 35 → 50 → 45 → 60

Result:

30, 20, 15, 5, 18, 25, 40, 35, 50, 45, 60

2️⃣ In-order Traversal (मध्य ऑर्डर)

Definition:
In-order traversal mein, hum pehle Left Subtree ko traverse karte hain, phir Root node ko visit karte hain, aur aakhir mein Right Subtree ko traverse karte hain.

• Order: Left → Root → Right

Algorithm:

1. Recursively call In-order on the Left subtree.
2. Visit the Root node. (Print the data)
3. Recursively call In-order on the Right subtree.

Important Note: BST mein In-order traversal hamesha Sorted Order mein values deta hai.

Aapke Example Tree Par:

• Left Subtree (Root 20): 5 → 15 → 18 → 20 → 25
• Root: 30
• Right Subtree (Root 40): 35 → 40 → 45 → 50 → 60

Result:

5, 15, 18, 20, 25, 30, 35, 40, 45, 50, 60

3️⃣ Post-order Traversal (बाद का ऑर्डर)

Definition:
Post-order traversal mein, hum pehle Left Subtree ko traverse karte hain, phir Right Subtree ko traverse karte hain, aur aakhir mein Root node ko visit karte hain.

• Order: Left → Right → Root

Algorithm:

1. Recursively call Post-order on the Left subtree.
2. Recursively call Post-order on the Right subtree.
3. Visit the Root node. (Print the data)

Aapke Example Tree Par:

• Left Subtree (Root 20): 5 → 18 → 15 → 25 → 20
• Right Subtree (Root 40): 35 → 45 → 60 → 50 → 40
• Root: 30

Result:

5, 18, 15, 25, 20, 35, 45, 60, 50, 40, 30