Binary Tree Inorder Traversal (Iterative)

To solve the iterative inorder traversal, I will simulate the recursive call stack using an explicit Stack object. The core logic follows the standard Inorder sequence: visit the left child, process the current node, then visit the right child. Since we cannot rely on the system stack, we need a manual approach. First, I initialize an empty stack and a pointer to the root. While the current pointer is not null or the stack is not empty, I push all left children onto the stack until I hit a null node. At this point, the top of the stack represents the leftmost unvisited node. I pop this node, add its value to my result list, and then set the current pointer to its right child. This effectively mimics returning from a recursive call. If the right child exists, the loop continues; otherwise, we pop again from the stack to visit the parent. For example, given a tree with root 1, left 2, and right 3, we push 1, then 2. We pop 2, add it, check 2's right (null), pop 1, add it, then move to 3. This ensures the order 2, 1, 3. The time complexity is O(n) since we touch each node twice at most. Space complexity is O(h), where h is the height of the tree, representing the maximum depth of our manual stack. This approach is robust for deep trees where recursion might cause a stack overflow, which aligns well with Microsoft's focus on production-ready, efficient algorithms.