Problem Statement:
Given the root of a binary tree, return the inorder traversal of its nodes values.
Examples:
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Initialize
- An empty
stackto simulate recursion. - A pointer
currstarting atroot.
- An empty
- Traverse Left: Keep pushing nodes to the stack while moving to the left child.
- Visit Node:
- When no more left nodes, pop from the stack.
- Add the node’s value to the result array
ans.
- Traverse Right: Move
currto the right child and repeat.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Initialize:
ans = []
stack = []
curr = root (1)
Main loop starts (curr || stack):
→ curr = 1
→ Inner loop: push 1 to stack → stack = [1]
→ move curr to left → curr = 2
→ Inner loop: push 2 to stack → stack = [1, 2]
→ move curr to left → curr = null
→ curr is null → pop from stack → curr = 2
→ ans.push(2) → ans = [2]
→ move curr to right → curr = 4
→ Inner loop: push 4 to stack → stack = [1, 4]
→ move curr to left → curr = null
→ curr is null → pop from stack → curr = 4
→ ans.push(4) → ans = [2, 4]
→ move curr to right → curr = null
→ curr is null → pop from stack → curr = 1
→ ans.push(1) → ans = [2, 4, 1]
→ move curr to right → curr = 3
→ Inner loop: push 3 to stack → stack = [3]
→ move curr to left → curr = null
→ curr is null → pop from stack → curr = 3
→ ans.push(3) → ans = [2, 4, 1, 3]
→ move curr to right → curr = null
Main loop ends (curr is null and stack is empty)
Traversal complete.
Final ans = [2, 4, 1, 3]
Output: Result: [2, 4, 1, 3]
var inorderTraversal = function(root) {
let ans = [];
let stack = [];
let curr = root;
while(curr || stack.length) {
while(curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
ans.push(curr.val);
curr = curr.right;
}
return ans;
};
def inorderTraversal(root):
ans = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
ans.append(curr.val)
curr = curr.right
return ans
public List inorderTraversal(TreeNode root) {
List ans = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
ans.add(curr.val);
curr = curr.right;
}
return ans;
}
vector inorderTraversal(TreeNode* root) {
vector ans;
stack stack;
TreeNode* curr = root;
while (curr || !stack.empty()) {
while (curr) {
stack.push(curr);
curr = curr->left;
}
curr = stack.top();
stack.pop();
ans.push_back(curr->val);
curr = curr->right;
}
return ans;
}
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int* ans = malloc(sizeof(int) * 1000); // allocate enough space
struct TreeNode* stack[1000];
int top = -1;
int size = 0;
struct TreeNode* curr = root;
while (curr || top != -1) {
while (curr) {
stack[++top] = curr;
curr = curr->left;
}
curr = stack[top--];
ans[size++] = curr->val;
curr = curr->right;
}
*returnSize = size;
return ans;
}
public IList InorderTraversal(TreeNode root) {
List ans = new List();
Stack stack = new Stack();
TreeNode curr = root;
while (curr != null || stack.Count > 0) {
while (curr != null) {
stack.Push(curr);
curr = curr.left;
}
curr = stack.Pop();
ans.Add(curr.val);
curr = curr.right;
}
return ans;
}
