Binary Tree Preorder Traversal

Preorder traversal of a binary tree is a classic problem where we visit the root node first, then traverse the left subtree, and finally traverse the right subtree. There are several ways to perform a preorder traversal, including both recursive and iterative methods.

1. Recursive Approach

We’ll define a recursive function that will handle the traversal of the tree, visiting the current node, then recursively calling itself on the left and right children.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        self.helper(root, result)
        return result

    def helper(self, node: Optional[TreeNode], result: List[int]):
        if node:
            result.append(node.val)  # Visit the current node
            self.helper(node.left, result)  # Traverse the left subtree
            self.helper(node.right, result) # Traverse the right subtree

2. Iterative Approach

We can also perform a preorder traversal using a stack. We’ll start by pushing the root node onto the stack and then continue by popping nodes from the stack, visiting them, and pushing their right and left children (in that order).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        stack = [root]
        result = []

        while stack:
            node = stack.pop()
            result.append(node.val) # Visit the current node
            if node.right:
                stack.append(node.right) # Push the right child onto the stack
            if node.left:
                stack.append(node.left)  # Push the left child onto the stack

        return result

Both of these approaches will return the preorder traversal of the binary tree and meet the problem’s constraints.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
def wrapper(root)
    if root.nil?
        return
    end

    @output << root.val

    wrapper(root.left)
    wrapper(root.right)
end

# @param {TreeNode} root
# @return {Integer[]}
def preorder_traversal(root)
    @output = []
    wrapper(root)
    @output
end

10 Prerequisite LeetCode Problems

“Binary Tree Preorder Traversal” is a basic problem dealing with binary trees and Preorder Traversal. It doesn’t necessarily require solving other problems first if you understand binary trees and tree traversal methods.

However, if you’re not yet comfortable with the concept of binary trees and their traversals, you may benefit from tackling the following problems to build up your understanding:

“Maximum Depth of Binary Tree” (LeetCode 104): This problem helps you understand the basics of navigating a binary tree and understanding its depth.
“Validate Binary Search Tree” (LeetCode 98): This will give you an understanding of the properties of Binary Search Trees and how to navigate and verify these properties.
“Symmetric Tree” (LeetCode 101): This problem involves traversing a binary tree and comparing nodes, which is a useful skill for tree traversal problems.
“Binary Tree Inorder Traversal” (LeetCode 94): This problem deals with a different type of tree traversal and will help further your understanding of how to traverse a tree.
“Binary Tree Postorder Traversal” (LeetCode 145): This is another type of tree traversal that it’s good to understand before tackling preorder traversal.

Each of these problems will help build your understanding and familiarity with binary trees and their traversal, which is the fundamental knowledge needed to solve the “Binary Tree Preorder Traversal” problem. You don’t necessarily need to solve all of these problems first, but it would be helpful.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

“Binary Tree Preorder Traversal” can be closely mapped to “Binary Tree Inorder Traversal”.

Both problems are about binary tree traversals that require knowledge of depth-first search (DFS). For the “Binary Tree Preorder Traversal”, the traversal sequence is root, left subtree, then right subtree. For the “Binary Tree Inorder Traversal”, the sequence is left subtree, root, then right subtree.

Although the visiting sequence differs, the concept of traversing a binary tree remains the same. By adjusting the order of operations, you can switch from one type of traversal to another.

“Binary Tree Inorder Traversal” is simpler since its output for a Binary Search Tree is sorted.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        head = root
        stack = []
        res = []

        while head or stack:
            if head:
                res.append(head.val)
                if head.right:
                    stack.append(head.right)
                head = head.left
            else:
                head = stack.pop()

        return res

Problem Classification

This problem can be classified as follows:

Data Structures: The problem involves manipulating and traversing a binary tree. Binary trees are a fundamental data structure used in computer science.
Tree Traversal: Specifically, this problem requires a specific type of tree traversal, called “preorder traversal”. In preorder traversal, each parent node is visited before its children.
Iterative Solutions: While tree traversals can often be implemented recursively, this problem asks for an iterative solution. This requires a good understanding of loops and conditionals.
Stack Usage: The iterative solution to this problem involves using a stack to keep track of nodes in the tree. Understanding how to use stack data structures is essential to solve this problem.

Language Agnostic Coding Drills

Understanding the Tree Traversal: Before attempting to solve this problem, a basic understanding of tree traversals is necessary. In this case, the specific traversal being performed is a preorder traversal (Root, Left, Right).
Understanding Data Structures (Stacks): For this problem, a stack is used. A stack is a linear data structure that follows the LIFO (Last In First Out) principle. Familiarize yourself with basic stack operations like push, pop, and peek.
Understanding Pointers: Understanding pointers and how to manipulate them is crucial. A pointer (like head in this case) is used to keep track of the current node being processed.
Using Stacks in Tree Traversal: The main learning point of this problem is understanding how to use a stack to perform the preorder traversal iteratively. We push nodes onto the stack during the traversal, and pop them when we need to revisit the nodes after exploring their left subtree.
Applying the Preorder Traversal Algorithm: Now that you know all the separate pieces, the next step is to implement the preorder traversal algorithm.

Here is a step-by-step process:

Start from the root node, and push it to the stack.
While the stack is not empty, perform the following operations:
- Pop a node from the stack. This is the current node.
- Add the current node’s value to the result list.
- If the current node has a right child, push it to the stack.
- If the current node has a left child, make this the current node and go back to the first step.
Repeat until the stack is empty.

Handle Empty Trees: You should also consider the edge case where the input tree is empty (the root is None). In this case, you should return an empty list.

By practicing each of these concepts individually, you’ll be able to combine them to solve this problem.

Targeted Drills in Python

Understanding the Tree Traversal

Before writing the code for tree traversal, you should know what a binary tree looks like. Here’s a simple representation of a binary tree node in Python:

1
2
3
4
5
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

For this simple exercise, let’s create a binary tree with some nodes and print the root value.

1
2
3
4
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(root.val)  # prints: 1

Understanding Data Structures (Stacks)

Next, let’s create a simple stack and perform basic operations like push, pop, and peek.

1
2
3
4
5
6
stack = []
stack.append(1)  # push
stack.append(2)  # push
print(stack[-1])  # peek: 2
print(stack.pop())  # pop: 2
print(stack.pop())  # pop: 1

Understanding Pointers
In Python, we don’t really have pointers, but we do work with references which can serve the same purpose in this context. Here’s an exercise using a simple pointer:
1 2 3 4 5
root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) head = root # 'head' is now a pointer to 'root' print(head.val) # prints: 1

Using Stacks in Tree Traversal

Let’s perform a simple iterative preorder traversal with the use of a stack. For now, we will only traverse the left side of the tree.

1
2
3
4
5
6
7
8
9
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
stack = []
head = root
while head:
    print(head.val)  # process current node
    stack.append(head)
    head = head.left  # move to left child

Applying the Preorder Traversal Algorithm

Now, we add the handling for the right child nodes in the traversal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
stack = []
head = root
while head or stack:
    if head:
        print(head.val)
        if head.right:
            stack.append(head.right)
        head = head.left
    else:
        head = stack.pop()

Handling Empty Trees

Finally, add a check to return immediately if the tree is empty:

1
2
3
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []

By practicing these drills, you can understand each part of the problem. After mastering each part, you can integrate them to solve the final problem.