Description:
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]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]Solution in Python:
To solve the problem of performing an inorder traversal of a binary tree iteratively in Python, we need to use a stack to simulate the recursive call stack used in the recursive approach.
Python
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# List to store the inorder traversal result
result = []
# Stack to keep track of nodes to be visited
stack = []
# Start with the root node
current = root
# Iterate until we have processed all nodes
while current or stack:
# Reach the leftmost node of the current node
while current:
stack.append(current)
current = current.left
# Current must be None at this point
current = stack.pop()
result.append(current.val)
# We have visited the node and its left subtree. Now, it's right subtree's turn
current = current.right
return resultExplanation of the Code:
- Initialization:
result: A list to store the values of nodes as we perform the inorder traversal.stack: A stack to keep track of nodes that need to be processed.current: A pointer to the current node we are processing, initialized toroot.
- Main Loop:
- The main loop runs as long as there are nodes to be processed (
currentis notNone) or there are nodes in the stack.
- The main loop runs as long as there are nodes to be processed (
- Processing the Left Subtree:
- We use a nested loop to reach the leftmost node of the current subtree. This involves pushing the current node onto the stack and moving to its left child.
- Visiting a Node:
- Once we reach a
Nonenode (meaning we’ve hit the end of the left subtree), we pop a node from the stack. - We add the value of this node to the
resultlist since we are visiting it (this is the “visit” part of the inorder traversal).
- Once we reach a
- Processing the Right Subtree:
- After visiting the node, we set
currentto its right child, if it exists, and repeat the process.
- After visiting the node, we set
- Returning the Result:
- Once the main loop finishes, we return the
resultlist which contains the inorder traversal of the binary tree.
- Once the main loop finishes, we return the
This iterative approach uses a stack to simulate the call stack used in a recursive inorder traversal, ensuring we visit nodes in the correct order: left child, current node, then right child.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
// List to store the inorder traversal result
const result = [];
// Stack to keep track of nodes to be visited
const stack = [];
// Start with the root node
let current = root;
// Iterate until we have processed all nodes
while (current !== null || stack.length > 0) {
// Reach the leftmost node of the current node
while (current !== null) {
stack.push(current);
current = current.left;
}
// Current must be null at this point
current = stack.pop();
result.push(current.val);
// We have visited the node and its left subtree. Now, it's right subtree's turn
current = current.right;
}
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// List to store the inorder traversal result
List<Integer> result = new ArrayList<>();
// Stack to keep track of nodes to be visited
Stack<TreeNode> stack = new Stack<>();
// Start with the root node
TreeNode current = root;
// Iterate until we have processed all nodes
while (current != null || !stack.isEmpty()) {
// Reach the leftmost node of the current node
while (current != null) {
stack.push(current);
current = current.left;
}
// Current must be null at this point
current = stack.pop();
result.add(current.val);
// We have visited the node and its left subtree. Now, it's right subtree's turn
current = current.right;
}
return result;
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public IList<int> InorderTraversal(TreeNode root) {
// List to store the inorder traversal result
List<int> result = new List<int>();
// Stack to manage the traversal
Stack<TreeNode> stack = new Stack<TreeNode>();
// Pointer to the current node
TreeNode current = root;
// Traverse the tree
while (current != null || stack.Count > 0) {
// Reach the leftmost node of the current node
while (current != null) {
stack.Push(current);
current = current.left;
}
// Current must be null at this point
current = stack.Pop();
result.Add(current.val); // Add the node value to the result
// Visit the right subtree
current = current.right;
}
return result; // Return the result of the inorder traversal
}
}