94. Binary Tree Inorder Traversal
Binary Tree Inorder Traversal (LeetCode 94) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Inorder Traversal subpattern.
How to solve Binary Tree Inorder Traversal
Binary Tree Inorder Traversal is a Inorder Traversal problem, part of Tree Traversal Patterns (DFS & BFS). Master inorder traversal for BST validation and kth element problems. Produces sorted order in BST.
Work towards the solution in these steps:
- Recall that inorder traversal visits left subtree, then root, then right subtree.
- A recursive solution is straightforward: traverse left, add root value, traverse right.
- For an iterative solution, use a stack to simulate the recursion.
The reference solution runs in O(n) time and O(1) space.
The Binary Tree Inorder Traversal solution and editorial walks through the full approach with reference code.
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]
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?
Topics and companies
Topics: Stack, Tree, Depth-First Search, Binary Tree.
Reported in interviews at Microsoft, Facebook, Oracle, Amazon, Google.
How to practise Binary Tree Inorder Traversal on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Binary Tree Inorder Traversal in the code editor, or read the Binary Tree Inorder Traversal editorial for a worked solution with its approach and complexity analysis.
Where Binary Tree Inorder Traversal sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Inorder Traversal subpattern
- The full DSA patterns sheet
Problems related to Binary Tree Inorder Traversal
Other problems that use the same Recursive Inorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Search Tree Iterator — Medium, same subpattern
- Delete Node in a BST — Medium, same subpattern
- Find Mode in Binary Search Tree — Easy, same subpattern
- Kth Smallest Element in a BST — Medium, same subpattern
- Minimum Absolute Difference in BST — Easy, same subpattern
- Validate Binary Search Tree — Medium, same subpattern
Binary Tree Inorder Traversal FAQ
What is the LeetCode number of Binary Tree Inorder Traversal?
Binary Tree Inorder Traversal is LeetCode problem 94, rated Easy.
What pattern is used to solve Binary Tree Inorder Traversal?
Binary Tree Inorder Traversal is a Inorder Traversal problem. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Inorder Traversal subpattern.
What is the time complexity of Binary Tree Inorder Traversal?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Binary Tree Inorder Traversal?
Binary Tree Inorder Traversal has been reported in interviews at Microsoft, Facebook, Oracle, Amazon, Google.