Problem

The problem is to find the inorder traversal of a binary tree.

In a binary tree, each node has at most two children - a left child and a right child.

The inorder traversal of a binary tree involves visiting the left child, then visiting the current node, and finally visiting the right child.

This operation should be performed recursively for all nodes in the tree.

Given the binary tree:

1
2
3   1
4    \
5     2
6    /
7   3

The inorder traversal would be: [1,3,2].

This problem also asks for a solution that uses iteration instead of recursion.

Walkthrough

The solution uses a stack to keep track of nodes to visit in the tree. The algorithm is as follows:

1. Start at the root node and insert its left children into the stack until there are no more left children.

2. Pop a node from the stack, visit it, and insert its right child (and any left children of the right child) into the stack.

3. Repeat step 2 until the stack is empty.

Example

Walk through the algorithm using the previous tree example.

Start with the root node 1. Since it doesn't have a left child, push it to the stack.

1
2
3Stack: [1]

Pop 1 from the stack, visit it, and push its right child 2 and its left child 3 to the stack.

1
2
3Visited: [1]
4Stack: [2, 3]

Pop 3 from the stack, visit it, and since it doesn't have any child, do nothing.

1
2
3Visited: [1, 3]
4Stack: [2]

Finally, pop 2 from the stack, visit it, and since it doesn't have a right child, do nothing.

1
2
3Visited: [1, 3, 2]
4Stack: []

When the stack is empty, the algorithm stops, and it returns the visited nodes as the inorder traversal of the tree: [1,3,2].

Solutions

Python

1
2python
3class Solution:
4    def inorderTraversal(self, root):
5        ans = []
6        stack = []
7
8        while root or stack:
9            while root:
10                stack.append(root)
11                root = root.left
12            root = stack.pop()
13            ans.append(root.val)
14            root = root.right
15
16        return ans

Java

1
2java
3public class Solution {
4    public List<Integer> inorderTraversal(TreeNode root) {
5        List<Integer> ans = new ArrayList<>();
6        Stack<TreeNode> stack = new Stack<>();
7
8        while (root != null || !stack.isEmpty()) {
9            while (root != null) {
10                stack.push(root);
11                root = root.left;
12            }
13            root = stack.pop();
14            ans.add(root.val);
15            root = root.right;
16        }
17
18        return ans;
19    }
20}

Javascript

1
2javascript
3var inorderTraversal = function(root) {
4    var ans = [];
5    var stack = [];
6
7    while (root || stack.length) {
8        while (root) {
9            stack.push(root);
10            root = root.left;
11        }
12        root = stack.pop();
13        ans.push(root.val);
14        root = root.right;
15    }
16
17    return ans;
18};

C++

1
2cpp
3class Solution {
4public:
5    vector<int> inorderTraversal(TreeNode* root) {
6        vector<int> ans;
7        stack<TreeNode*> stack;
8
9        while (root || !stack.empty()) {
10            while (root) {
11                stack.push(root);
12                root = root->left;
13            }
14            root = stack.top();
15            stack.pop();
16            ans.push_back(root->val);
17            root = root->right;
18        }
19
20        return ans;
21    }
22};

C#

1
2csharp
3public class Solution {
4    public IList<int> InorderTraversal(TreeNode root) {
5        IList<int> ans = new List<int>();
6        Stack<TreeNode> stack = new Stack<TreeNode>();
7
8        while (root != null || stack.Count > 0) {
9            while (root != null) {
10                stack.Push(root);
11                root = root.left;
12            }
13            root = stack.Pop();
14            ans.Add(root.val);
15            root = root.right;
16        }
17
18        return ans;
19    }
20}

These are all iterative solutions to the problem. In each language, a stack data structure is used to keep track of all nodes to visit.

The Python solution uses a list to emulate a stack, with append for push operations and pop for pop operations. root or stack checks if either the current node is not null or the stack is not empty. This is equivalent to root != null || !stack.isEmpty() in Java and root || stack.length in Javascript.

The Java solution is almost identical but it uses the ArrayList and Stack classes from the Java Collections Framework.

The Javascript solution, similar to Python, uses an array as a stack. The length of the array is used to check if the stack is empty.

The C++ solution uses the vector and stack from the C++ Standard Template Library. stack.empty() is used to check if the stack is empty.

The C# solution is similar to the Java solution in use of a stack and list to store results. It uses LINQ (Language Integrated Query) to perform operations on the data structures.

In all solutions, the essential logic is the same. The algorithm pushes nodes to the stack until the leftmost node is reached, then pops and visits nodes while moving right as long as possible. This is repeated until both the current node is null and the stack is empty. The visited nodes are returned as the inorder traversal of the tree.