Binary Tree Inorder Traversal

Binary Tree Inorder Traversal 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.

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
• All coding practice problems

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
• 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
• All Nodes Distance K in Binary Tree — Medium, same pattern