{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Binary Tree Preorder Traversal – Solution & Complexity

Interview solutions
/
Binary Tree Preorder Traversal

Solution Walkthrough

  1. Step 1: Recognize the preorder pattern

    Preorder traversal always does the same three actions at every node: record the current node, traverse the left subtree, then traverse the right subtree. That makes this a standard depth-first search problem with a deterministic visit order.

  2. Step 2: Recursive DFS solution

    Use a helper DFS that stops on None, appends the current node's value first, then recursively processes the left child and the right child. This matches the definition of preorder traversal directly.

    def preorder_traversal(root: TreeNode) -> list[int]:
    result = []

    def dfs(node):
        if node is None:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return result

  3. Step 3: Iterative stack solution and complexity

    Time: O(n) because each node is visited exactly once. Space: O(h) for the explicit stack, where h is the tree height (O(n) in the worst skewed case). This stack-based preorder traversal is an optimal approach that avoids recursion depth concerns: pop a node, record it, then push its right child before its left child so the left subtree is processed first.

    def preorder_traversal(root: TreeNode) -> list[int]:
    if root is None:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

    return result

FAQ

See also

Practice Binary Tree Preorder Traversal online (run code in the browser)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Balanced Binary Tree solution (easy)Diameter of Binary Tree solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?