DSA Series Chapter 14 – INORDER TRAVERSAL (BINARY TREE)(Python Version)

on

 [Join Our Blog] 

DSA Series Chapter 14 – INORDER TRAVERSAL (BINARY TREE)(Python Version)

1. Inorder Traversal (Quick Recall)

Traversal Order:

Left → Root → Right

Category:

  • Depth First Traversal (DFS)

2. Binary Tree Used (Same as C Version)

            1
          /   \
         2     3
        / \
       4   5

Expected Inorder Output:

4 2 5 1 3

3. Python Node Structure

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

4. Inorder Traversal – Recursive Algorithm (Python)

Logic (Plain English)

  1. If node is None, return

  2. Traverse left subtree

  3. Visit root node

  4. Traverse right subtree

5. Python Program – Recursive Inorder Traversal

def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

6. Complete Executable Python Program

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

# Tree creation
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Inorder Traversal:")
inorder(root)

Output

Inorder Traversal:
4 2 5 1 3

7. Dry Run (Recursive Call Flow)

inorder(1)
 └── inorder(2)
     └── inorder(4) → print 4
     → print 2
     └── inorder(5) → print 5
 → print 1
 └── inorder(3) → print 3

8. Time and Space Complexity

Time Complexity

  • O(n) — every node visited once

Space Complexity

  • O(h) — recursion stack
    where h = height of tree

    • Skewed tree → O(n)

    • Balanced tree → O(log n)

9. Important Concept (Exam-Focused)

Inorder traversal of a Binary Search Tree (BST) gives sorted output.

⚠ This is NOT true for a normal binary tree.

10. Common Student Mistakes

  • Printing root before left subtree (becomes preorder)

  • Assuming inorder output is always sorted

  • Forgetting base condition (root is None)

11. Practice Questions

  1. Write inorder traversal for a right-skewed tree.

  2. What is inorder output of a single-node tree?

  3. Explain why BST inorder traversal is sorted.

  4. Convert recursive inorder traversal to iterative in Python.

ALSO CHECK 

DS(Data Structure) Python&C Edition

DSA Series Chapter 1 Time & Space Complexity ( C Edition)

DSA Series Chapter 2 Arrays  (C Version)


DSA Series Chapter 2 Arrays  (Python Version)

DSA Series Chapter 3 Strings (C Version)


DSA Series Chapter 3 Strings (Python Version)


DSA Series Chapter 4 Linked Lists (Python Version)


DSA Series Chapter 4 Linked Lists (C Version)


DSA Series Chapter 5 Stacks (Python Version)


DSA Series Chapter 5  Stacks  (C Version)




















DSA Series Chapter 13 - Binary Tree traversal, BFS, DFT/DFS, Preorder Traversal In Binary Tree



 







Tail Recursion Optimization: How Compilers Convert Recursion Into Iteration


Advanced Recursion: Memoization vs. Tabulation — The Deep Optimization Blueprint for Professionals


Advanced Sorting Algorithms: Merge Sort Internals — Merge Tree, Cache Behavior & Real Cost Analysis


Enjoyed this post? [Follow here] for daily coding insights.



Comments

Post a Comment