How hard is LeetCode 94. Binary Tree Inorder Traversal?

LeetCode 94. Binary Tree Inorder Traversal is rated Easy on LeetCode.

What is the time complexity of LeetCode 94. Binary Tree Inorder Traversal?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 94. Binary Tree Inorder Traversal?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 94. Binary Tree Inorder Traversal cover?

LeetCode 94. Binary Tree Inorder Traversal is tagged Stack, Tree, Depth-First Search and Binary Tree on LeetCode.

Binary Tree Inorder Traversal — LeetCode 94 Python Solution

EasyStackTreeDepth-First SearchBinary Tree

Problem: #94
Pattern: Stack
Reading time: 3 min
Source: leetcode.com

The problem

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

Python solution

Python

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 94. Binary Tree Inorder Traversal is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 94. Binary Tree Inorder Traversal?: LeetCode 94. Binary Tree Inorder Traversal is rated Easy on LeetCode.
What is the time complexity of LeetCode 94. Binary Tree Inorder Traversal?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 94. Binary Tree Inorder Traversal?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 94. Binary Tree Inorder Traversal cover?: LeetCode 94. Binary Tree Inorder Traversal is tagged Stack, Tree, Depth-First Search and Binary Tree on LeetCode.