Coding Exercise: Inorder Tree Traversal Using Recursion

Traverse binary tree: Left subtree → Root → Right subtree.

Example: Tree(1,2,3) → Output: 2,1,3

Problem Statement

Input: Binary tree root

Output: Inorder traversal (vector or print)

Order: Left → Root → Right ✓

Binary Tree Node Class

              
            
C++

          Tree node structure
        
struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Recursive Inorder Solution

              
            
C++

          Complete inorder traversal
        
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void inorder(Node* root) {
    if (root == nullptr) return;
    
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    // Tree:     1
    //          / \
    //         2   3
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    
    cout << "Inorder: ";
    inorder(root);  // 2 1 3
    return 0;
}

Traversal Visualization

              
            
TEXT

          Tree traversal path
        
Tree:    4
        /   \
       2     6
      / \   / \
     1   3 5   7

Inorder: 1→2→3→4→5→6→7
Path:    L→L→R→Root→L→R→Root

Test Cases

              
            
TEXT

          Expected outputs
        
Tree(1,2,3) → 2 1 3
Tree(5,null,7) → 5 7
Single node → 10
Empty → (nothing)

Other Traversals (Bonus)

              
            
C++

          Preorder and Postorder
        
void preorder(Node* root) {  // Root L R
    if (!root) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

void postorder(Node* root) {  // L R Root
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Complexity

Time: O(n) - visit each node once

Space: O(h) - recursion stack (h=height)

Practice Variations

1. Preorder/postorder traversal

2. Level order (iterative)

3. Height of tree recursively

Conclusion

Mastered tree recursion! Inorder = sorted order for BST.

Next: Backtracking or graph DFS.