Leetcode: 94. Binary Tree Inorder Traversal (Stack)

Inorder Traversal of a Binary Tree in C++

Introduction

In this blog post, we will discuss the implementation of an algorithm to perform an inorder traversal on a binary tree. The goal is to return the inorder traversal of its nodes' values. We will provide a step-by-step explanation of the code and discuss its complexity analysis. Let's dive into the details!

Problem Statement

Given the root of a binary tree, we need to return the inorder traversal of its nodes' values. The inorder traversal visits the left subtree, then the current node, and finally the right subtree.

Solution Overview

To perform an inorder traversal iteratively, we can use a stack-based approach. We push the nodes onto the stack until we reach the leftmost node. Then, we pop the node from the stack, add its value to the result vector, and move to its right child. We repeat this process until the stack becomes empty.

Solution Implementation

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector res;
        stack stack;
        TreeNode* curr = root;
        while (curr != nullptr || !stack.empty()) {
            while (curr != nullptr) {
                stack.push(curr);
                curr = curr->left;
            }
            curr = stack.top();
            stack.pop();
            res.push_back(curr->val);
            curr = curr->right;
        }
        return res;
    }
};
  

The function inorderTraversal takes the root of the binary tree as input and returns a vector res containing the inorder traversal of the tree. We start with an empty result vector and a stack to maintain the traversal order. We also initialize a pointer curr to the root of the tree.

The algorithm uses a while loop to traverse the tree. Inside the loop, we push the nodes onto the stack until we reach the leftmost node. Then, we pop the node from the stack, add its value to the result vector, and move to its right child. We repeat this process until the stack becomes empty.

Finally, we return the result vector res containing the inorder traversal of the binary tree.

Complexity Analysis

The time complexity of the iterative inorder traversal algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited once, and each node is pushed and popped from the stack exactly once.

The space complexity is O(h), where h is the height of the binary tree. In the worst case, the stack can store all nodes of the left subtree, resulting in O(n) space complexity for a skewed tree. However, for a balanced tree, the space complexity is O(log n) since the maximum number of nodes in the stack at any point is the height of the tree.

Conclusion

In this blog post, we explored an iterative solution to perform an inorder traversal on a binary tree using a stack. The algorithm provides a space-efficient and iterative approach to traverse the tree in the desired order. We provided a step-by-step explanation of the code, discussed the complexity analysis, and introduced the stack-based approach for inorder traversal.