LeetCode 144 - Binary Tree Preorder Traversal

This problem asks us to return the preorder traversal of a binary tree. A binary tree consists of nodes where each node may have a left child and a right child. The input root represents the root node of that tree.

leetcodeeasystacktreedepth-first-searchbinary-tree

LeetCode Problem 144

Difficulty: 🟢 Easy
Topics: Stack, Tree, Depth-First Search, Binary Tree

Solution

LeetCode 144, Binary Tree Preorder Traversal

Problem Understanding

This problem asks us to return the preorder traversal of a binary tree.

A binary tree consists of nodes where each node may have a left child and a right child. The input root represents the root node of that tree.

In a preorder traversal, nodes are visited in the following order:

  1. Visit the current node
  2. Traverse the left subtree
  3. Traverse the right subtree

For example, consider this tree:

    1
     \
      2
     /
    3

The preorder traversal is:

[1, 2, 3]

because we first visit 1, then move to the right child 2, then visit 2's left child 3.

The output should be a list containing node values in preorder order.

The constraints are relatively small, with at most 100 nodes. This means even recursive solutions are completely safe from recursion depth issues in practice. However, the follow up explicitly asks for an iterative solution, so we should understand both recursive and stack based approaches.

Several edge cases are important:

  • The tree may be empty, meaning root = [] or root = None
  • The tree may contain only one node
  • The tree may be completely skewed left or right
  • Some nodes may have only one child

A correct solution must handle all these structures without missing nodes or visiting nodes in the wrong order.

Approaches

Brute Force Approach, Recursive DFS

The most direct solution uses recursion.

Since preorder traversal naturally follows the pattern:

  1. Process current node
  2. Recurse into left subtree
  3. Recurse into right subtree

we can implement the traversal exactly as defined.

At each node:

  • Add the current node's value to the result
  • Recursively process the left child
  • Recursively process the right child

This works because recursion implicitly uses the call stack to remember where to return after finishing each subtree.

Although this solution is already efficient enough for the constraints, interviewers often consider the recursive approach "trivial" because it directly mirrors the traversal definition.

Optimal Approach, Iterative DFS Using a Stack

The iterative solution simulates recursion manually using a stack.

The key insight is that recursion internally uses a call stack. We can reproduce the same traversal order ourselves.

In preorder traversal, we always want to process:

  1. Current node
  2. Left subtree
  3. Right subtree

Since a stack is Last In First Out, we must push the right child before the left child. That way, the left child is processed first when popped from the stack.

The algorithm becomes:

  • Start with the root node in the stack
  • Pop a node
  • Add its value to the result
  • Push its right child
  • Push its left child

This guarantees preorder ordering.

Approach Time Complexity Space Complexity Notes
Brute Force Recursive DFS O(n) O(h) Uses recursion stack, simple and intuitive
Optimal Iterative DFS O(n) O(h) Uses explicit stack, avoids recursion

Here:

  • n is the number of nodes
  • h is the height of the tree

In the worst case of a skewed tree, h = n.

Algorithm Walkthrough

Iterative Preorder Traversal

  1. Initialize an empty result list.

This list stores the preorder traversal as we process nodes. 2. Handle the empty tree case.

If root is None, return an empty list immediately. 3. Create a stack and push the root node onto it.

The stack keeps track of nodes we still need to process. 4. Repeat while the stack is not empty.

Each iteration processes one node. 5. Pop the top node from the stack.

This is the next node in preorder order. 6. Add the node's value to the result list.

In preorder traversal, the current node is visited before its children. 7. Push the right child onto the stack if it exists.

We push the right child first because stacks are Last In First Out. 8. Push the left child onto the stack if it exists.

Since the left child is pushed last, it will be processed first, preserving preorder ordering. 9. Continue until the stack becomes empty.

At this point, all nodes have been visited exactly once. 10. Return the result list.

Why it works

The algorithm maintains the invariant that the stack contains nodes whose subtrees still need to be traversed in preorder order.

By pushing the right child before the left child, we ensure the left subtree is processed first when nodes are popped from the stack. Since each node is visited before its children, the traversal order becomes:

node -> left subtree -> right subtree

which exactly matches preorder traversal.

Python Solution

# 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

from typing import List, Optional

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()

            result.append(node.val)

            if node.right:
                stack.append(node.right)

            if node.left:
                stack.append(node.left)

        return result

The implementation begins by checking whether the tree is empty. If root is None, the function immediately returns an empty list.

The result list stores the traversal output, while the stack simulates recursive DFS behavior.

Inside the loop, we pop the top node and immediately append its value to the result because preorder traversal visits the current node first.

Next, we push the right child before the left child. This ordering is essential. Since stacks process the most recently added element first, pushing the left child last ensures it gets processed before the right child.

The loop continues until every node has been processed.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    result := []int{}
    stack := []*TreeNode{root}

    for len(stack) > 0 {
        lastIndex := len(stack) - 1
        node := stack[lastIndex]
        stack = stack[:lastIndex]

        result = append(result, node.Val)

        if node.Right != nil {
            stack = append(stack, node.Right)
        }

        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }

    return result
}

The Go implementation follows the same logic as the Python solution.

Instead of Python lists, Go uses slices for both the result and the stack.

Go uses nil instead of None for missing pointers. The stack is implemented as a slice of *TreeNode.

To pop from the stack, we retrieve the last element and shrink the slice using slicing syntax.

There are no integer overflow concerns because node values are very small according to the constraints.

Worked Examples

Example 1

Input:

root = [1,null,2,3]

Tree:

    1
     \
      2
     /
    3

Initial state:

Step Stack Result
Start [1] []

Process node 1:

Step Stack Result
Pop 1 [] [1]
Push 2 [2] [1]

Process node 2:

Step Stack Result
Pop 2 [] [1, 2]
Push 3 [3] [1, 2]

Process node 3:

Step Stack Result
Pop 3 [] [1, 2, 3]

Final answer:

[1, 2, 3]

Example 2

Input:

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

Tree:

         1
       /   \
      2     3
     / \     \
    4   5     8
       / \   /
      6   7 9

Traversal sequence:

Step Current Node Result
1 1 [1]
2 2 [1, 2]
3 4 [1, 2, 4]
4 5 [1, 2, 4, 5]
5 6 [1, 2, 4, 5, 6]
6 7 [1, 2, 4, 5, 6, 7]
7 3 [1, 2, 4, 5, 6, 7, 3]
8 8 [1, 2, 4, 5, 6, 7, 3, 8]
9 9 [1, 2, 4, 5, 6, 7, 3, 8, 9]

Final answer:

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

Example 3

Input:

root = []

Initial state:

Step Stack Result
Start [] []

Since the tree is empty, we immediately return:

[]

Example 4

Input:

root = [1]

Initial state:

Step Stack Result
Start [1] []

Process node 1:

Step Stack Result
Pop 1 [] [1]

Final answer:

[1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Stack stores at most the tree height worth of nodes

The algorithm processes each node a single time, so the running time is linear in the number of nodes.

The space complexity depends on the maximum number of nodes simultaneously stored in the stack. In a balanced tree, this is proportional to the height of the tree, which is O(log n). In the worst case of a completely skewed tree, the stack may contain O(n) nodes.

Test Cases

# Definition for testing
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):
        if not root:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()

            result.append(node.val)

            if node.right:
                stack.append(node.right)

            if node.left:
                stack.append(node.left)

        return result

sol = Solution()

# Empty tree
assert sol.preorderTraversal(None) == []  # tests empty input

# Single node
root = TreeNode(1)
assert sol.preorderTraversal(root) == [1]  # tests single element tree

# Right skewed tree
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
assert sol.preorderTraversal(root) == [1, 2, 3]  # tests preorder ordering

# Left skewed tree
root = TreeNode(1, TreeNode(2, TreeNode(3)))
assert sol.preorderTraversal(root) == [1, 2, 3]  # tests deep left recursion pattern

# Full binary tree
root = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7))
)
assert sol.preorderTraversal(root) == [1, 2, 4, 5, 3, 6, 7]  # tests balanced tree

# Tree with missing children
root = TreeNode(
    1,
    TreeNode(2, None, TreeNode(4)),
    TreeNode(3)
)
assert sol.preorderTraversal(root) == [1, 2, 4, 3]  # tests sparse tree structure

# Larger mixed tree
root = TreeNode(
    10,
    TreeNode(5, TreeNode(2), TreeNode(7)),
    TreeNode(15, None, TreeNode(20))
)
assert sol.preorderTraversal(root) == [10, 5, 2, 7, 15, 20]  # tests mixed branching
Test Why
Empty tree Validates handling of None input
Single node Ensures simplest non empty tree works
Right skewed tree Verifies preorder traversal with only right children
Left skewed tree Verifies preorder traversal with only left children
Full binary tree Tests standard balanced traversal
Tree with missing children Ensures sparse trees are handled correctly
Larger mixed tree Tests general correctness on irregular structure

Edge Cases

Empty Tree

An empty tree is represented by root = None.

This case can easily cause errors if the algorithm assumes the root always exists. Attempting to access root.val when root is None would raise an exception.

The implementation handles this immediately with:

if not root:
    return []

This guarantees safe execution for empty inputs.

Single Node Tree

A tree containing only one node is the smallest valid non empty tree.

Some implementations accidentally skip processing because they rely too heavily on child existence checks.

Our solution correctly initializes the stack with the root node, processes it once, and returns the single value.

Highly Skewed Tree

A tree may resemble a linked list where every node has only one child.

For example:

1
 \
  2
   \
    3

This case is important because recursive solutions may risk deep recursion in larger problems. The iterative solution avoids recursion entirely and handles skewed trees naturally using the explicit stack.

The traversal still correctly follows preorder order because nodes are always processed before their children.

Nodes With Missing Children

Many binary trees are sparse, meaning some nodes have only one child.

Incorrect implementations sometimes attempt to push None values onto the stack or recurse into missing children unnecessarily.

This implementation checks:

if node.right:

and

if node.left:

before pushing children onto the stack, ensuring only valid nodes are processed.