Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the root of a binary tree, return the inorder traversal of its nodes’ values. In inorder traversal, we visit nodes in the following order: left subtree -> root -> right subtree.
Input:
- Root of a binary tree
Output:
- List of integers representing the inorder traversal
Constraints:
- The number of nodes in the tree is in the range [0, 100]
- -100 ≤ Node.val ≤ 100
Examples:
Example 1:
1
\
2
/
3
Input: root = [1,null,2,3,null,null,null]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
1
/ \
2 3
/ \
4 5
Input: root = [1,2,3,4,5]
Output: [4,2,5,1,3]
Explanation: Visit left subtree(4,2,5), then root(1), then right subtree(3)
Solutions
Approach 1: Recursive Solution
The most intuitive approach using recursion following the natural definition of inorder traversal.
Algorithm:
- Recursively traverse the left subtree
- Visit the root node (add to result)
- Recursively traverse the right subtree
Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root):
"""
Recursive inorder traversal
Time: O(N) where N is number of nodes
Space: O(H) where H is height of tree (recursion stack)
"""
result = []
def dfs(node):
if not node:
return
dfs(node.left) # Traverse left subtree
result.append(node.val) # Visit root
dfs(node.right) # Traverse right subtree
dfs(root)
return result
def inorderTraversalCompact(root):
"""
Compact recursive solution
Time: O(N)
Space: O(H)
"""
if not root:
return []
return (inorderTraversalCompact(root.left) +
[root.val] +
inorderTraversalCompact(root.right))
Java:
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
/**
* Recursive inorder traversal
* Time: O(N)
* Space: O(H)
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result);
return result;
}
private void dfs(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
dfs(node.left, result); // Traverse left subtree
result.add(node.val); // Visit root
dfs(node.right, result); // Traverse right subtree
}
/**
* Compact recursive solution
* Time: O(N)
* Space: O(H)
*/
public List<Integer> inorderTraversalCompact(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
result.addAll(inorderTraversalCompact(root.left));
result.add(root.val);
result.addAll(inorderTraversalCompact(root.right));
return result;
}
}
Go:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// inorderTraversal - Recursive inorder traversal
// Time: O(N)
// Space: O(H)
func inorderTraversal(root *TreeNode) []int {
result := []int{}
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left) // Traverse left subtree
result = append(result, node.Val) // Visit root
dfs(node.Right) // Traverse right subtree
}
dfs(root)
return result
}
// inorderTraversalCompact - Compact recursive solution
// Time: O(N)
// Space: O(H)
func inorderTraversalCompact(root *TreeNode) []int {
if root == nil {
return []int{}
}
result := inorderTraversalCompact(root.Left)
result = append(result, root.Val)
result = append(result, inorderTraversalCompact(root.Right)...)
return result
}
JavaScript:
class TreeNode {
constructor(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
}
/**
* Recursive inorder traversal
* Time: O(N)
* Space: O(H)
*/
function inorderTraversal(root) {
const result = [];
function dfs(node) {
if (!node) {
return;
}
dfs(node.left); // Traverse left subtree
result.push(node.val); // Visit root
dfs(node.right); // Traverse right subtree
}
dfs(root);
return result;
}
/**
* Compact recursive solution
* Time: O(N)
* Space: O(H)
*/
function inorderTraversalCompact(root) {
if (!root) {
return [];
}
return [...inorderTraversalCompact(root.left),
root.val,
...inorderTraversalCompact(root.right)];
}
C#:
using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
/// <summary>
/// Recursive inorder traversal
/// Time: O(N)
/// Space: O(H)
/// </summary>
public IList<int> InorderTraversal(TreeNode root) {
List<int> result = new List<int>();
Dfs(root, result);
return result;
}
private void Dfs(TreeNode node, List<int> result) {
if (node == null) {
return;
}
Dfs(node.left, result); // Traverse left subtree
result.Add(node.val); // Visit root
Dfs(node.right, result); // Traverse right subtree
}
/// <summary>
/// Compact recursive solution
/// Time: O(N)
/// Space: O(H)
/// </summary>
public IList<int> InorderTraversalCompact(TreeNode root) {
List<int> result = new List<int>();
if (root == null) {
return result;
}
result.AddRange(InorderTraversalCompact(root.left));
result.Add(root.val);
result.AddRange(InorderTraversalCompact(root.right));
return result;
}
}
Approach 2: Iterative Solution using Stack
Use an explicit stack to simulate the recursion call stack. This is more complex for inorder than preorder.
Algorithm:
- Use a stack to track nodes
- Start with root and go as far left as possible, pushing nodes to stack
- When no more left children, pop from stack, visit node, and go to right child
- Repeat until stack is empty and no current node
Python:
def inorderTraversalIterative(root):
"""
Iterative inorder traversal using stack
Time: O(N)
Space: O(H)
"""
result = []
stack = []
current = root
while stack or current:
# Go to the leftmost node
while current:
stack.append(current)
current = current.left
# Current is None here, so pop from stack
current = stack.pop()
result.append(current.val) # Visit node
# Move to right subtree
current = current.right
return result
def inorderTraversalIterativeV2(root):
"""
Alternative iterative approach with explicit state tracking
Time: O(N)
Space: O(H)
"""
if not root:
return []
result = []
stack = [(root, False)] # (node, is_visited)
while stack:
node, visited = stack.pop()
if visited:
# Node has been processed, add to result
result.append(node.val)
else:
# Process node: right, node (visited), left
if node.right:
stack.append((node.right, False))
stack.append((node, True)) # Mark as visited
if node.left:
stack.append((node.left, False))
return result
Java:
public List<Integer> inorderTraversalIterative(TreeNode root) {
/**
* Iterative inorder traversal using stack
* Time: O(N)
* Space: O(H)
*/
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (!stack.isEmpty() || current != null) {
// Go to the leftmost node
while (current != null) {
stack.push(current);
current = current.left;
}
// Current is null here, so pop from stack
current = stack.pop();
result.add(current.val); // Visit node
// Move to right subtree
current = current.right;
}
return result;
}
class NodeState {
TreeNode node;
boolean visited;
NodeState(TreeNode node, boolean visited) {
this.node = node;
this.visited = visited;
}
}
public List<Integer> inorderTraversalIterativeV2(TreeNode root) {
/**
* Alternative iterative approach with explicit state tracking
* Time: O(N)
* Space: O(H)
*/
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<NodeState> stack = new Stack<>();
stack.push(new NodeState(root, false));
while (!stack.isEmpty()) {
NodeState current = stack.pop();
if (current.visited) {
// Node has been processed, add to result
result.add(current.node.val);
} else {
// Process node: right, node (visited), left
if (current.node.right != null) {
stack.push(new NodeState(current.node.right, false));
}
stack.push(new NodeState(current.node, true)); // Mark as visited
if (current.node.left != null) {
stack.push(new NodeState(current.node.left, false));
}
}
}
return result;
}
Go:
// inorderTraversalIterative - Iterative inorder traversal using stack
// Time: O(N)
// Space: O(H)
func inorderTraversalIterative(root *TreeNode) []int {
result := []int{}
stack := []*TreeNode{}
current := root
for len(stack) > 0 || current != nil {
// Go to the leftmost node
for current != nil {
stack = append(stack, current)
current = current.Left
}
// Current is nil here, so pop from stack
current = stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, current.Val) // Visit node
// Move to right subtree
current = current.Right
}
return result
}
type NodeState struct {
node *TreeNode
visited bool
}
// inorderTraversalIterativeV2 - Alternative iterative approach with explicit state tracking
// Time: O(N)
// Space: O(H)
func inorderTraversalIterativeV2(root *TreeNode) []int {
if root == nil {
return []int{}
}
result := []int{}
stack := []NodeState{{root, false}}
for len(stack) > 0 {
current := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if current.visited {
// Node has been processed, add to result
result = append(result, current.node.Val)
} else {
// Process node: right, node (visited), left
if current.node.Right != nil {
stack = append(stack, NodeState{current.node.Right, false})
}
stack = append(stack, NodeState{current.node, true}) // Mark as visited
if current.node.Left != nil {
stack = append(stack, NodeState{current.node.Left, false})
}
}
}
return result
}
JavaScript:
/**
* Iterative inorder traversal using stack
* Time: O(N)
* Space: O(H)
*/
function inorderTraversalIterative(root) {
const result = [];
const stack = [];
let current = root;
while (stack.length > 0 || current) {
// Go to the leftmost node
while (current) {
stack.push(current);
current = current.left;
}
// Current is null here, so pop from stack
current = stack.pop();
result.push(current.val); // Visit node
// Move to right subtree
current = current.right;
}
return result;
}
/**
* Alternative iterative approach with explicit state tracking
* Time: O(N)
* Space: O(H)
*/
function inorderTraversalIterativeV2(root) {
if (!root) {
return [];
}
const result = [];
const stack = [[root, false]]; // [node, isVisited]
while (stack.length > 0) {
const [node, visited] = stack.pop();
if (visited) {
// Node has been processed, add to result
result.push(node.val);
} else {
// Process node: right, node (visited), left
if (node.right) {
stack.push([node.right, false]);
}
stack.push([node, true]); // Mark as visited
if (node.left) {
stack.push([node.left, false]);
}
}
}
return result;
}
C#:
public IList<int> InorderTraversalIterative(TreeNode root) {
/// <summary>
/// Iterative inorder traversal using stack
/// Time: O(N)
/// Space: O(H)
/// </summary>
List<int> result = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (stack.Count > 0 || current != null) {
// Go to the leftmost node
while (current != null) {
stack.Push(current);
current = current.left;
}
// Current is null here, so pop from stack
current = stack.Pop();
result.Add(current.val); // Visit node
// Move to right subtree
current = current.right;
}
return result;
}
public IList<int> InorderTraversalIterativeV2(TreeNode root) {
/// <summary>
/// Alternative iterative approach with explicit state tracking
/// Time: O(N)
/// Space: O(H)
/// </summary>
List<int> result = new List<int>();
if (root == null) {
return result;
}
Stack<(TreeNode node, bool visited)> stack = new Stack<(TreeNode, bool)>();
stack.Push((root, false));
while (stack.Count > 0) {
var (node, visited) = stack.Pop();
if (visited) {
// Node has been processed, add to result
result.Add(node.val);
} else {
// Process node: right, node (visited), left
if (node.right != null) {
stack.Push((node.right, false));
}
stack.Push((node, true)); // Mark as visited
if (node.left != null) {
stack.Push((node.left, false));
}
}
}
return result;
}
Approach 3: Morris Traversal (Space Optimized)
Use Morris traversal to achieve O(1) space complexity by creating temporary links.
Python:
def inorderTraversalMorris(root):
"""
Morris inorder traversal with O(1) space
Time: O(N)
Space: O(1)
"""
result = []
current = root
while current:
if not current.left:
# No left child, visit and go right
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
# First time visiting, create link
predecessor.right = current
current = current.left
else:
# Second time visiting, remove link and visit
predecessor.right = None
result.append(current.val)
current = current.right
return result
Java:
public List<Integer> inorderTraversalMorris(TreeNode root) {
/**
* Morris inorder traversal with O(1) space
* Time: O(N)
* Space: O(1)
*/
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// No left child, visit and go right
result.add(current.val);
current = current.right;
} else {
// Find inorder predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// First time visiting, create link
predecessor.right = current;
current = current.left;
} else {
// Second time visiting, remove link and visit
predecessor.right = null;
result.add(current.val);
current = current.right;
}
}
}
return result;
}
Go:
// inorderTraversalMorris - Morris inorder traversal with O(1) space
// Time: O(N)
// Space: O(1)
func inorderTraversalMorris(root *TreeNode) []int {
result := []int{}
current := root
for current != nil {
if current.Left == nil {
// No left child, visit and go right
result = append(result, current.Val)
current = current.Right
} else {
// Find inorder predecessor
predecessor := current.Left
for predecessor.Right != nil && predecessor.Right != current {
predecessor = predecessor.Right
}
if predecessor.Right == nil {
// First time visiting, create link
predecessor.Right = current
current = current.Left
} else {
// Second time visiting, remove link and visit
predecessor.Right = nil
result = append(result, current.Val)
current = current.Right
}
}
}
return result
}
JavaScript:
/**
* Morris inorder traversal with O(1) space
* Time: O(N)
* Space: O(1)
*/
function inorderTraversalMorris(root) {
const result = [];
let current = root;
while (current) {
if (!current.left) {
// No left child, visit and go right
result.push(current.val);
current = current.right;
} else {
// Find inorder predecessor
let predecessor = current.left;
while (predecessor.right && predecessor.right !== current) {
predecessor = predecessor.right;
}
if (!predecessor.right) {
// First time visiting, create link
predecessor.right = current;
current = current.left;
} else {
// Second time visiting, remove link and visit
predecessor.right = null;
result.push(current.val);
current = current.right;
}
}
}
return result;
}
C#:
public IList<int> InorderTraversalMorris(TreeNode root) {
/// <summary>
/// Morris inorder traversal with O(1) space
/// Time: O(N)
/// Space: O(1)
/// </summary>
List<int> result = new List<int>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// No left child, visit and go right
result.Add(current.val);
current = current.right;
} else {
// Find inorder predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// First time visiting, create link
predecessor.right = current;
current = current.left;
} else {
// Second time visiting, remove link and visit
predecessor.right = null;
result.Add(current.val);
current = current.right;
}
}
}
return result;
}
Key Insights
- Visit Order: Inorder visits left subtree, then root, then right subtree (Left → Root → Right)
- BST Property: For BST, inorder traversal returns sorted sequence
- Iterative Complexity: More complex than preorder due to delayed visiting
- Stack Pattern: Push left nodes first, then process and move right
Edge Cases
- Empty tree: Return empty list
- Single node: Return list with one element
- Left skewed tree: Deep recursion/stack
- Right skewed tree: Shallow recursion/stack
- BST: Results in sorted order
Common Mistakes
- Wrong visit order: Visiting root before left subtree
- Stack management: Not properly handling the left-first traversal
- Morris implementation: Incorrect predecessor finding or link management
- Base case: Not handling null nodes properly
- BST assumption: Assuming all trees are BSTs
Follow-up Questions
- BST validation: Use inorder to check if tree is valid BST
- Kth smallest: Find kth smallest element in BST using inorder
- Recovery: Recover BST where two nodes were swapped
- Predecessor/Successor: Find inorder predecessor/successor
- Range queries: Get values in BST within a range using inorder