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

Tree Traversals Inorder Preorder Postorder

In this page:

  1. Preorder
  2. Inorder
  3. Postorder
  4. Traversal Comparison
  5. Traversal Practice

Preorder

Preorder traversal visits the current node first, then recursively traverses its entire left subtree, then its entire right subtree — this order is useful when you need to process a node before its children, such as copying a tree structure.

Example: 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 visits the left subtree first, then the current node, then the right subtree — applied to a binary search tree specifically, this produces the values in fully sorted order, which is inorder's most important practical use.

Example: 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 visits the left subtree, then the right subtree, then the current node last — this order is useful whenever children need to be fully processed before their parent, such as safely deleting a tree or computing subtree sizes.

Example: 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

The three orders differ only in when the current node itself is visited relative to its two subtrees — choosing the right one depends entirely on what you need to know about the children before or after processing the parent.

Example: 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

All three traversals share the same simple recursive structure, just with the 'visit node' step moved to a different position — tracing a small tree by hand with each of the three orders is the fastest way to build intuition for how they differ.

Example: 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;
}
🔒

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.