We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Preorder Traversal

Difficulty: Easy

Problem Description

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

Key Insights

  • Preorder traversal visits nodes in the order: root, left subtree, right subtree.
  • Both recursive and iterative approaches can be used to achieve the traversal.
  • Using a stack allows us to simulate the recursive nature of tree traversal in an iterative manner.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as we visit each node once. Space Complexity: O(h) - where h is the height of the tree, due to the stack used in the iterative approach or the recursion stack in the recursive approach.

Solution

The problem can be solved using both recursive and iterative methods.

  1. Recursive Approach: This is straightforward. We define a function that visits the root, then recursively visits the left and right children.

  2. Iterative Approach: We use a stack to keep track of nodes. We push the root onto the stack, then repeatedly pop from the stack to visit nodes, pushing right children first so that left children are processed next.

Code Solutions

def preorderTraversal(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:  # Push right child first
            stack.append(node.right)
        if node.left:   # Push left child next
            stack.append(node.left)
    
    return result
← Back to All Questions