DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Binary Tree Inorder Traversal - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

# 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]:
        result = []

        def inorder(node):
            if not node:
                return 

            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
        
        inorder(root)
        return result

Complexity Analysis

Here, n is the number of nodes, and h is the height of the binary tree.

  • Time Complexity: O(n)
    • Each node is visited during traversal.
  • Space Complexity: O(n)
    • Output space: O(n) — to store the final inorder traversal result (list of node values)
    • Stack space: O(h) — for the recursion stack.
      • In the best case (a balanced tree), h = log n.
      • In the worst case (a skewed tree), h = n, so the recursion stack uses O(n) space.

# 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]:
        res = []
        stack = []
        
        cur = root
        while cur or stack:
            # Go as left as possible
            while cur:
                stack.append(cur)
                cur = cur.left

            # Process the node
            cur = stack.pop()
            res.append(cur.val)

            # Go to the right subtree
            cur = cur.right
        return res

Complexity Analysis

Here, n is the number of nodes, and h is the height of the binary tree.

  • Time Complexity: O(n)
    • Each node is visited during traversal.
  • Space Complexity: O(n)
    • Output space: O(n) — to store the final inorder traversal result (list of node values)
    • Stack space: O(h) — for the explicit stack used in traversal. In the worst case, h can be up to n.