DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Binary Tree Preorder 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def preorder(node):
            if not node:
                return None

            result.append(node.val)
            preorder(node.left)
            preorder(node.right)
            
        preorder(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 preorder 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = [root]
        
        while stack:
            cur = stack.pop()
            if cur:
                result.append(cur.val)
                stack.append(cur.right)
                stack.append(cur.left)
        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 preorder 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.