Inorder Traversal of a Binary Tree

Given a binary tree, print the Inorder traversal of the given tree.
Inorder traversal is a common operation on a binary tree where we visit the nodes in a specific order: left subtree, root node, and then the right subtree. This traversal method is particularly useful for binary search trees (BST) because it retrieves the node values in ascending order.

Input-Output Examples

Example 1:

Input:

plaintext
  1
   \
    2
   /
  3

Output: 1, 3, 2

Example 2:

Input:

plaintext
    4
   / \
  2   5
 / \
1   3

Output: 1, 2, 3, 4, 5

Example 3:

Input:

plaintext
  3
 / \
1   4
 \
  2

Output: 1, 2, 3, 4

Approach:

Inorder traversal can be performed either recursively or iteratively. The recursive approach is straightforward, but the iterative approach is often preferred in environments where stack space is a concern.

Technique and steps to implement:

  • Data Structures Used: Stack (for iterative approach).
  • Traversal Order: Left, Root, Right.
  1. Recursive Approach:
    • Traverse the left subtree.
    • Visit the root node.
    • Traverse the right subtree.
  2. Iterative Approach:
    • Use a stack to mimic the recursive call stack.
    • Traverse the left subtree iteratively by pushing nodes onto the stack.
    • Visit the root node by popping from the stack.
    • Traverse the right subtree.

C++ Program for Inorder Traversal of a Binary Tree

cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stack;
        TreeNode* current = root;
        
        while (current != NULL || !stack.empty()) {
            while (current != NULL) {
                stack.push(current);
                current = current->left;
            }
            current = stack.top();
            stack.pop();
            result.push_back(current->val);
            current = current->right;
        }
        
        return result;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    Solution sol;
    vector<int> result = sol.inorderTraversal(root);
    for (int val : result) {
        cout << val << " ";
    }
    return 0;
}

Java Program for Inorder Traversal of a Binary Tree

java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        Solution sol = new Solution();
        List<Integer> result = sol.inorderTraversal(root);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python Program for Inorder Traversal of a Binary Tree

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root: TreeNode):
        result = []
        stack = []
        current = root
        
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right
        
        return result

# Example usage
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)

sol = Solution()
result = sol.inorderTraversal(root)
print(result)  # Output: [1, 3, 2]

DSA

4974

598

Related Articles