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.

Description Solution Video 14:42

94. Binary Tree Inorder Traversal

Easy80.4% acceptance7 companies

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?

Asked at 7 companies

Anduril Amazon Microsoft

Google Meta Bloomberg

TCS

Topics

14:42

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

Similar problems

Validate Binary Search TreeMedium Binary Tree Preorder TraversalEasy Binary Tree Postorder TraversalEasy Binary Search Tree IteratorMedium Kth Smallest Element in a BSTMedium Closest Binary Search Tree Value IIHard Inorder Successor in BSTMedium Convert Binary Search Tree to Sorted Doubly Linked ListMedium

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3Case 4

Input

[1,null,2,3]

Input

[1,2,3,4,5,null,8,null,null,6,7,9]

Input

[]

Input

[1]

Your code is saved on this device.Solution