← Back to DSA Course | Chapter 11: Trees | Lesson 2 of 10

Tree Traversals यानि Inorder, Preorder, Postorder

Tree traversals एक family tree के चारों ओर चलने के तीन अलग तरीके हैं: एक parent को इसके kids से पहले, बीच में, या बाद में visit करना।

In this page:

  1. Preorder
  2. Inorder
  3. Postorder
  4. Traversal Comparison
  5. Traversal Practice
Syntax
markup 
def preorder(node):
    if node:
        visit(node)
        preorder(node.left)
        preorder(node.right)

# inorder: left, visit, right
# postorder: left, right, visit

Preorder

Preorder traversal पहले current node visit करता है, फिर recursively इसका पूरा left subtree traverse करता है, फिर इसका पूरा right subtree — यह order उपयोगी है जब आपको किसी node को इसके children से पहले process करना हो, जैसे एक tree structure copy करना।

उदाहरण: Preorder

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
void preorder(Node* n) {
    if (!n) return;
    cout << n->val << " ";
    preorder(n->left);
    preorder(n->right);
}
int main() {
    Node c1 = {2, nullptr, nullptr}, c2 = {3, nullptr, nullptr};
    Node root = {1, &c1, &c2};
    preorder(&root);
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void preorder(Node n) {
        if (n == null) return;
        System.out.print(n.val + " ");
        preorder(n.left);
        preorder(n.right);
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        preorder(root);
    }
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def preorder(n):
    if n is None:
        return
    print(n.val, end=" ")
    preorder(n.left)
    preorder(n.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
preorder(root)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void preorder(struct Node* n) {
    if (!n) return;
    printf("%d ", n->val);
    preorder(n->left);
    preorder(n->right);
}
int main() {
    struct Node c1 = {2, NULL, NULL}, c2 = {3, NULL, NULL};
    struct Node root = {1, &c1, &c2};
    preorder(&root);
    return 0;
}

Inorder

Inorder traversal पहले left subtree visit करता है, फिर current node, फिर right subtree — एक binary search tree पर specifically apply किया जाए, यह values को पूरी तरह sorted order में produce करता है, जो inorder का सबसे महत्वपूर्ण practical उपयोग है।

उदाहरण: Inorder

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
void inorder(Node* n) {
    if (!n) return;
    inorder(n->left);
    cout << n->val << " ";
    inorder(n->right);
}
int main() {
    Node c1 = {1, nullptr, nullptr}, c2 = {3, nullptr, nullptr};
    Node root = {2, &c1, &c2};
    inorder(&root);
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void inorder(Node n) {
        if (n == null) return;
        inorder(n.left);
        System.out.print(n.val + " ");
        inorder(n.right);
    }
    public static void main(String[] args) {
        Node root = new Node(2);
        root.left = new Node(1);
        root.right = new Node(3);
        inorder(root);
    }
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(n):
    if n is None:
        return
    inorder(n.left)
    print(n.val, end=" ")
    inorder(n.right)

root = Node(2)
root.left = Node(1)
root.right = Node(3)
inorder(root)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void inorder(struct Node* n) {
    if (!n) return;
    inorder(n->left);
    printf("%d ", n->val);
    inorder(n->right);
}
int main() {
    struct Node c1 = {1, NULL, NULL}, c2 = {3, NULL, NULL};
    struct Node root = {2, &c1, &c2};
    inorder(&root);
    return 0;
}

Postorder

Postorder traversal left subtree visit करता है, फिर right subtree, फिर current node आखिर में — यह order तब उपयोगी है जब children को उनके parent से पहले पूरी तरह process करना हो, जैसे एक tree को सुरक्षित रूप से delete करना या subtree sizes compute करना।

उदाहरण: Postorder

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
void postorder(Node* n) {
    if (!n) return;
    postorder(n->left);
    postorder(n->right);
    cout << n->val << " ";
}
int main() {
    Node c1 = {2, nullptr, nullptr}, c2 = {3, nullptr, nullptr};
    Node root = {1, &c1, &c2};
    postorder(&root);
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void postorder(Node n) {
        if (n == null) return;
        postorder(n.left);
        postorder(n.right);
        System.out.print(n.val + " ");
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        postorder(root);
    }
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def postorder(n):
    if n is None:
        return
    postorder(n.left)
    postorder(n.right)
    print(n.val, end=" ")

root = Node(1)
root.left = Node(2)
root.right = Node(3)
postorder(root)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void postorder(struct Node* n) {
    if (!n) return;
    postorder(n->left);
    postorder(n->right);
    printf("%d ", n->val);
}
int main() {
    struct Node c1 = {2, NULL, NULL}, c2 = {3, NULL, NULL};
    struct Node root = {1, &c1, &c2};
    postorder(&root);
    return 0;
}

Traversal Comparison

तीनों orders सिर्फ इसमें अलग हैं कि current node खुद इसके दो subtrees के सापेक्ष कब visit होता है — सही चुनना पूरी तरह इस पर निर्भर करता है कि parent process करने से पहले या बाद में आपको children के बारे में क्या जानना है।

उदाहरण: Traversal Comparison

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
void pre(Node* n){ if(!n) return; cout<<n->val<<" "; pre(n->left); pre(n->right); }
void in(Node* n){ if(!n) return; in(n->left); cout<<n->val<<" "; in(n->right); }
void post(Node* n){ if(!n) return; post(n->left); post(n->right); cout<<n->val<<" "; }
int main() {
    Node c1={1,nullptr,nullptr}, c2={3,nullptr,nullptr};
    Node root={2,&c1,&c2};
    cout<<"pre: "; pre(&root); cout<<"\nin: "; in(&root); cout<<"\npost: "; post(&root);
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void pre(Node n){ if(n==null) return; System.out.print(n.val+" "); pre(n.left); pre(n.right); }
    static void in(Node n){ if(n==null) return; in(n.left); System.out.print(n.val+" "); in(n.right); }
    static void post(Node n){ if(n==null) return; post(n.left); post(n.right); System.out.print(n.val+" "); }
    public static void main(String[] args) {
        Node root = new Node(2);
        root.left = new Node(1);
        root.right = new Node(3);
        System.out.print("pre: "); pre(root);
        System.out.print("\nin: "); in(root);
        System.out.print("\npost: "); post(root);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def pre(n):
    if n is None: return
    print(n.val, end=" "); pre(n.left); pre(n.right)

def inorder(n):
    if n is None: return
    inorder(n.left); print(n.val, end=" "); inorder(n.right)

def post(n):
    if n is None: return
    post(n.left); post(n.right); print(n.val, end=" ")

root = Node(2)
root.left = Node(1)
root.right = Node(3)
print("pre:", end=" "); pre(root)
print("\nin:", end=" "); inorder(root)
print("\npost:", end=" "); post(root)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void pre(struct Node* n){ if(!n) return; printf("%d ",n->val); pre(n->left); pre(n->right); }
void in(struct Node* n){ if(!n) return; in(n->left); printf("%d ",n->val); in(n->right); }
void post(struct Node* n){ if(!n) return; post(n->left); post(n->right); printf("%d ",n->val); }
int main() {
    struct Node c1={1,NULL,NULL}, c2={3,NULL,NULL};
    struct Node root={2,&c1,&c2};
    printf("pre: "); pre(&root);
    printf("\nin: "); in(&root);
    printf("\npost: "); post(&root);
    return 0;
}

Traversal Practice

तीनों traversals वही simple recursive structure share करते हैं, बस 'visit node' step एक अलग position पर move हुआ — तीनों orders में से हर एक से हाथ से एक छोटी tree trace करना यह intuition बनाने का सबसे तेज़ तरीका है कि वे कैसे अलग हैं।

उदाहरण: Traversal Practice

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
void inorder(Node* n) { if(!n) return; inorder(n->left); cout<<n->val<<" "; inorder(n->right); }
int main() {
    Node c1={1,nullptr,nullptr}, c3={3,nullptr,nullptr}, c2={2,&c1,&c3};
    Node root={4,&c2,nullptr};
    inorder(&root);
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void inorder(Node n) { if(n==null) return; inorder(n.left); System.out.print(n.val+" "); inorder(n.right); }
    public static void main(String[] args) {
        Node c1 = new Node(1), c3 = new Node(3);
        Node c2 = new Node(2); c2.left = c1; c2.right = c3;
        Node root = new Node(4); root.left = c2;
        inorder(root);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def inorder(n):
    if n is None: return
    inorder(n.left); print(n.val, end=" "); inorder(n.right)

c1, c3 = Node(1), Node(3)
c2 = Node(2); c2.left, c2.right = c1, c3
root = Node(4); root.left = c2
inorder(root)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void inorder(struct Node* n) { if(!n) return; inorder(n->left); printf("%d ",n->val); inorder(n->right); }
int main() {
    struct Node c1={1,NULL,NULL}, c3={3,NULL,NULL}, c2={2,&c1,&c3};
    struct Node root={4,&c2,NULL};
    inorder(&root);
    return 0;
}
Related Topics

Binary Tree परिचय · Binary Search Tree क्या है · AVL Tree क्या है · Tree की Height और Diameter

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. कौन सी line पहले आती है इसे mix up करना: preorder recursive calls से पहले visit करता है, inorder बीच में, postorder बाद में।
  2. if (!n) return; base case भूल जाना, जो nullptr dereference करता है।
  3. किसी भी binary tree पर inorder से sorted output की उम्मीद करना, जब यह सिर्फ एक BST पर काम करता है।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Binary Tree Introduction Next Lesson → Level Order Traversal BFS

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.