Last updated on January 29th, 2025 at 02:18 am
Here, we see a Binary Tree Inorder Traversal LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table, Stack, Tree
Companies
Microsoft
Level of Question
Easy

Binary Tree Inorder Traversal LeetCode Solution
Table of Contents
1. Problem Statement
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]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided code snippets is Tree Depth First Search (DFS). Specifically, it is an Inorder Traversal of a binary tree, which visits nodes in the order: Left -> Root -> Right. This traversal is implemented either iteratively (using a stack) or recursively.
3. Code Implementation in Different Languages
3.1 Binary Tree Inorder Traversal C++
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> nodes; stack<TreeNode*> todo; while (root || !todo.empty()) { while (root) { todo.push(root); root = root -> left; } root = todo.top(); todo.pop(); nodes.push_back(root -> val); root = root -> right; } return nodes; } };
3.2 Binary Tree Inorder Traversal Java
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); dfsTraversal(list, root); return list; } private boolean dfsTraversal(List<Integer> list, TreeNode root) { if(root == null){ return true; } if(dfsTraversal(list, root.left)){ list.add(root.val); } return dfsTraversal(list, root.right); } }
3.3 Binary Tree Inorder Traversal JavaScript
var inorderTraversal = function(root) { const stack = []; const res = []; while (root || stack.length) { if (root) { stack.push(root); root = root.left; } else { root = stack.pop(); res.push(root.val); root = root.right; } } return res; };
3.4 Binary Tree Inorder Traversal Python
class Solution(object): def inorderTraversal(self, root): result, stack = [], [(root, False)] while stack: cur, visited = stack.pop() if cur: if visited: result.append(cur.val) else: stack.append((cur.right, False)) stack.append((cur, True)) stack.append((cur.left, False)) return result
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n) | O(h) |
Java | O(n) | O(h) |
JavaScript | O(n) | O(h) |
Python | O(n) | O(h) |
where,
n is the number of nodes in the binary tree.
h is the height of the binary tree. In the worst case (skewed tree), h = n. In the best case (balanced tree), h = log(n).
- The time complexity is O(n) because each node is visited exactly once.
- The space complexity is O(h) because the stack (or recursion stack) stores at most h nodes at any given time.