algoadvance

Leetcode 94. Binary Tree Inorder Traversal

Problem Statement

You are given the root of a binary tree. Implement an inorder traversal of the binary tree and return the values of the nodes in the traversal order.

Clarifying Questions

  1. Can the tree be empty?
    • Yes, if the tree is empty, return an empty list.
  2. What is the structure of the tree nodes?
    • Each node contains an integer value and pointers to its left and right children.
  3. Do we need to account for duplicate values in the tree?
    • Yes, nodes can have duplicate values.

Strategy

Inorder traversal of a binary tree visits nodes in the following order:

  1. Visit the left subtree
  2. Visit the current node
  3. Visit the right subtree

We can implement this both recursively and iteratively. Here, we will focus on the iterative approach using a stack, which is a more common interview question variant.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

#include <vector>
#include <stack>

// Iterative approach using stack
class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> s;
        TreeNode* current = root;
        
        while (current != nullptr || !s.empty()) {
            // Reach the leftmost Node of the current Node
            while (current != nullptr) {
                s.push(current);
                current = current->left;
            }
            // Current must be NULL at this point
            current = s.top();
            s.pop();
            result.push_back(current->val); // Visit the node

            // We have visited the node and its left subtree. Now it's the right subtree's turn
            current = current->right;
        }
        return result;
    }
};

Time Complexity

The time complexity of this algorithm is (O(n)), where (n) is the number of nodes in the binary tree. Each node is visited exactly once.

The space complexity is also (O(n)) for the stack in the worst case, especially when the tree is completely unbalanced, i.e., each node has only one child (all left or all right nodes).

This structure ensures an efficient and clear solution to the problem using an iterative approach, which is often preferred in environments where recursion depth might be a concern.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI