Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Binary Tree Inorder Traversal solution and explanation

EasyBinary TreeDepth-First SearchStackTree7 min read80.4% acceptanceUpdated 9 Apr 2026
Asked atAndurilAmazonMicrosoftGoogleMetaBloomberg
+1 moreTCS
Practise Binary Tree Inorder Traversal
14:42
Iterative & Recursive - Binary Tree Inorder Traversal - Leetcode 94 - PythonNeetCode · 14:42 · 158K viewsWatch on YouTube
9 more videos on this problem
  1. Iterative & Recursive - Binary Tree Inorder Traversal - Leetcode 94 - PythonNeetCode · 14:42 · 158K views
  2. LeetCode Binary Tree Inorder Traversal Solution Explained - JavaNick White · 8:44 · 96K views
  3. LeetCode 94. Binary Tree Inorder Traversal ITERATIVELY - Interview Prep Ep 75Fisher Coder · 10:53 · 12K views
  4. LeetCode Solution - 94 Binary Tree Inorder Traversal | Morris Traversal Algorithm JavascriptThinkFWD · 19:06 · 10K views
  5. LeetCode 94. Binary Tree Inorder Traversal RECURSIVELY - Interview Prep Ep 66Fisher Coder · 7:49 · 5K views
  6. Binary Tree Inorder Traversal | Java | LeetCode Solution 94Tech Tutor · 7:43 · 5K views
  7. [Java] Leetcode 94. Binary Tree Inorder Traversal (Iteratively & Recursively) [Binary Tree #2]Eric Programming · 10:54 · 3K views
  8. How To Solve "94 Binary Tree Inorder Traversal" on LeetCode - JavaScript EasyBecoming A Better Dev (with David) · 6:01 · 1K views
  9. Binary Tree Inorder Traversal - Recursive Leetcode 94Persistent Programmer · 8:08 · 944 views
  10. Binary Tree Inorder Traversal | Binary Tree | Python | Iterative Approach | LeetCode 94Ace Leetcode · 8:18 · 678 views

The problem

Given the root of a binary tree, return the inorder traversal of its nodes' values.

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
Follow up: Recursive solution is trivial, could you do it iteratively?

Approach overview

Problem Overview: Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder means you always visit the left subtree, then the current node, then the right subtree.

Approach 1: Recursive Inorder Traversal (O(n) time, O(h) space)

This approach uses recursion to follow the natural definition of inorder traversal. Starting from the root, recursively traverse the left child, append the current node value to the result array, then recursively traverse the right child. The recursion stack implicitly handles the traversal order. Each node is visited exactly once, giving O(n) time complexity. The space complexity is O(h), where h is the height of the tree, due to the recursion call stack. This method is the cleanest and easiest to implement when working with tree traversal problems.

Approach 2: Iterative Inorder Traversal Using Stack (O(n) time, O(h) space)

This method simulates recursion using an explicit stack. Start from the root and repeatedly push nodes while moving to the leftmost child. When no more left children exist, pop the top node from the stack, record its value, and move to its right child. Repeat the process until both the stack is empty and the current node is null. Each node is pushed and popped at most once, so the traversal runs in O(n) time. The stack holds at most the height of the tree, giving O(h) space. This technique is common in iterative depth-first search implementations.

Recommended for interviews: Interviewers expect you to know both approaches. The recursive version shows you understand tree traversal fundamentals and DFS ordering. The iterative stack solution demonstrates stronger control over execution flow and the ability to convert recursion into an explicit data structure. Many interviewers ask for the iterative version after seeing the recursive solution.

Approach 1: Recursive Inorder Traversal

This approach uses recursion to traverse the binary tree. Inorder traversal involves visiting the left subtree, the root node, and then the right subtree. The base case for the recursion is to return if the current node is null.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root):
        result = []
        self.inorder(root, result)
        return result

    def inorder(self, root, result):
        if root is not None:
            self.inorder(root.left, result)
            result.append(root.val)
            self.inorder(root.right, result)
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public 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;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode root, List<Integer> result) {
        if (root == null) return;
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

void inorder(TreeNode* root, vector<int>& result) {
    if (!root) return;
    inorder(root->left, result);
    result.push_back(root->val);
    inorder(root->right, result);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    inorder(root, result);
    return result;
}
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function inorderTraversal(root) {
    const result = [];
    const inorder = (node) => {
        if (!node) return;
        inorder(node.left);
        result.push(node.val);
        inorder(node.right);
    };
    inorder(root);
    return result;
}
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void inorderTraversalHelper(struct TreeNode* root, int* returnSize, int* result) {
    if (!root) return;
    inorderTraversalHelper(root->left, returnSize, result);
    result[(*returnSize)++] = root->val;
    inorderTraversalHelper(root->right, returnSize, result);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* result = (int*)malloc(100 * sizeof(int));
    inorderTraversalHelper(root, returnSize, result);
    return result;
}
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 {
    public IList<int> InorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        Inorder(root, result);
        return result;
    }

    private void Inorder(TreeNode node, List<int> result) {
        if (node == null) return;
        Inorder(node.left, result);
        result.Add(node.val);
        Inorder(node.right, result);
    }
}

The Python solution uses a class-based approach with two methods. The inorderTraversal method initializes the result list and invokes a recursive inorder method to populate the list with the node values following an inorder sequence.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)

Try this approach in the editor

Approach 2: Iterative Inorder Traversal

In this approach, we use a stack to perform an iterative inorder traversal. The stack is utilized to track the nodes to be visited. This method mimics the recursive behavior by explicitly using a stack to push left children until reaching a null entry, then processes the nodes and explores the right subtrees.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root):
        result, stack = [], []
        current = root
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right
        return result
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {
    public 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;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }
}
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stack;
    TreeNode* current = root;
    while (current != nullptr || !stack.empty()) {
        while (current != nullptr) {
            stack.push(current);
            current = current->left;
        }
        current = stack.top();
        stack.pop();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function inorderTraversal(root) {
    let result = [], stack = [];
    let current = root;
    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    return result;
}
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct Stack {
    struct TreeNode* data;
    struct Stack* next;
};

void push(struct Stack** top, struct TreeNode* node) {
    struct Stack* new_node = (struct Stack*)malloc(sizeof(struct Stack));
    new_node->data = node;
    new_node->next = *top;
    *top = new_node;
}

struct TreeNode* pop(struct Stack** top) {
    if (*top == NULL) return NULL;
    struct TreeNode* node = (*top)->data;
    struct Stack* temp = *top;
    *top = (*top)->next;
    free(temp);
    return node;
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    struct Stack* stack = NULL;
    int* result = (int*)malloc(100 * sizeof(int));
    *returnSize = 0;
    struct TreeNode* current = root;
    while (current != NULL || stack != NULL) {
        while (current != NULL) {
            push(&stack, current);
            current = current->left;
        }
        current = pop(&stack);
        result[(*returnSize)++] = current->val;
        current = current->right;
    }
    return result;
}
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 {
    public IList<int> InorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        while (current != null || stack.Count > 0) {
            while (current != null) {
                stack.Push(current);
                current = current.left;
            }
            current = stack.Pop();
            result.Add(current.val);
            current = current.right;
        }
        return result;
    }
}

Python's solution uses lists to manage the stack of nodes in place of a recursive method. The traversal ensures all elements are processed correctly in the inorder sequence.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)

Try this approach in the editor

Approach 3: Recursive Traversal

We first recursively traverse the left subtree, then visit the root node, and finally recursively traverse the right subtree.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree, and the space complexity mainly depends on the stack space of the recursive call.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    const dfs = (root: TreeNode | null) => {
        if (!root) {
            return;
        }
        dfs(root.left);
        ans.push(root.val);
        dfs(root.right);
    };
    dfs(root);
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		ans = append(ans, root.Val)
		dfs(root.Right)
	}
	dfs(root)
	return
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, ans: &mut Vec<i32>) {
        if root.is_none() {
            return;
        }
        let node = root.as_ref().unwrap().borrow();
        Self::dfs(&node.left, ans);
        ans.push(node.val);
        Self::dfs(&node.right, ans);
    }

    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = vec![];
        Self::dfs(&root, &mut ans);
        ans
    }
}
Try this approach in the editor

Approach 4: Stack Implementation for Non-recursive Traversal

The non-recursive approach is as follows:

  1. Define a stack stk.
  2. Push the left nodes of the tree into the stack in sequence.
  3. When the left node is null, pop and process the top element of the stack.
  4. Repeat steps 2-3.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree, and the space complexity mainly depends on the stack space.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    const stk: TreeNode[] = [];
    const ans: number[] = [];
    while (root || stk.length > 0) {
        if (root) {
            stk.push(root);
            root = root.left;
        } else {
            root = stk.pop();
            ans.push(root.val);
            root = root.right;
        }
    }
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
	stk := []*TreeNode{}
	for root != nil || len(stk) > 0 {
		if root != nil {
			stk = append(stk, root)
			root = root.Left
		} else {
			root = stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			ans = append(ans, root.Val)
			root = root.Right
		}
	}
	return
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn inorder_traversal(mut root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = vec![];
        let mut stk = vec![];
        while root.is_some() || !stk.is_empty() {
            if root.is_some() {
                let next = root.as_mut().unwrap().borrow_mut().left.take();
                stk.push(root);
                root = next;
            } else {
                let mut node = stk.pop().unwrap();
                let mut node = node.as_mut().unwrap().borrow_mut();
                ans.push(node.val);
                root = node.right.take();
            }
        }
        ans
    }
}
Try this approach in the editor

Approach 5: Morris Implementation for In-order Traversal

Morris traversal does not require a stack, so the space complexity is O(1). The core idea is:

Traverse the binary tree nodes,

  1. If the left subtree of the current node root is null, add the current node value to the result list ans, and update the current node to root.right.
  2. If the left subtree of the current node root is not null, find the rightmost node prev of the left subtree (which is the predecessor node of the root node in in-order traversal):
    • If the right subtree of the predecessor node prev is null, point the right subtree of the predecessor node to the current node root, and update the current node to root.left.
    • If the right subtree of the predecessor node prev is not null, add the current node value to the result list ans, then point the right subtree of the predecessor node to null (i.e., disconnect prev and root), and update the current node to root.right.
  3. Repeat the above steps until the binary tree node is null, and the traversal ends.

The time complexity is O(n), and the space complexity is O(1). Here, n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    while (root) {
        if (!root.left) {
            ans.push(root.val);
            root = root.right;
        } else {
            let prev = root.left;
            while (prev.right && prev.right != root) {
                prev = prev.right;
            }
            if (!prev.right) {
                prev.right = root;
                root = root.left;
            } else {
                ans.push(root.val);
                prev.right = null;
                root = root.right;
            }
        }
    }
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
	for root != nil {
		if root.Left == nil {
			ans = append(ans, root.Val)
			root = root.Right
		} else {
			prev := root.Left
			for prev.Right != nil && prev.Right != root {
				prev = prev.Right
			}
			if prev.Right == nil {
				prev.Right = root
				root = root.Left
			} else {
				ans = append(ans, root.Val)
				prev.Right = nil
				root = root.Right
			}
		}
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Inorder Traversal

Time Complexity: O(n)

Space Complexity: O(n)

Iterative Inorder Traversal

Time Complexity: O(n)

Space Complexity: O(n)

Recursive Traversal–
Stack Implementation for Non-recursive Traversal–
Morris Implementation for In-order Traversal–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive Inorder TraversalO(n)O(h)Best for readability and quick implementation when recursion is allowed
Iterative Traversal with StackO(n)O(h)Preferred when avoiding recursion or when interviewers ask for iterative DFS

Frequently asked questions

Is Binary Tree Inorder Traversal easy or hard?

Binary Tree Inorder Traversal is considered an easy problem because it focuses on a fundamental DFS traversal pattern. However, it forms the foundation for many medium and hard tree problems, making it essential to master early.

How to solve Binary Tree Inorder Traversal in O(n)?

Traverse the tree using depth‑first search while maintaining the inorder order: left subtree, current node, then right subtree. Either use recursion to naturally follow this order or simulate it iteratively with a stack that tracks nodes while moving left through the tree.

Binary Tree Inorder Traversal Python or Java solution?

Python and Java implementations both follow the same logic: recursively visit the left child, record the node value, then visit the right child. Iterative solutions use a stack to push nodes while traversing left, then pop nodes to process them and move to the right subtree.

What is the best approach for Binary Tree Inorder Traversal?

Both recursive DFS and iterative stack traversal are optimal for this problem. Each visits every node exactly once, giving O(n) time complexity. The recursive solution is shorter and easier to write, while the iterative stack approach demonstrates deeper understanding of traversal mechanics and is often preferred in interviews.

Is Binary Tree Inorder Traversal asked at Google/Amazon/Meta?

Binary tree traversal problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often build on this concept, such as validating a BST, recovering a BST, or converting a tree to a sorted sequence using inorder traversal.

What data structure is used in Binary Tree Inorder Traversal?

The recursive approach relies on the call stack, while the iterative approach explicitly uses a stack data structure. The stack keeps track of nodes whose right subtrees still need to be visited after finishing their left subtree.

What is the time complexity of Binary Tree Inorder Traversal?

Binary Tree Inorder Traversal runs in O(n) time because every node in the tree is visited exactly once. Whether using recursion or an explicit stack, each node is processed a single time during the traversal.

Comments

Next problem · similarValidate Binary Search TreeMedium
Now write it yourselfClose this page and solve Binary Tree Inorder Traversal in the editor, without looking.
Practise Binary Tree Inorder Traversal