Leetcode – Binary Tree Preorder Traversal Solution in Python

In computer science, trees are one of the most versatile and commonly used data structures. Among trees, binary trees hold a special place due to their extensive applications. One essential operation on binary trees is traversal, and within traversal algorithms, preorder traversal is a fundamental approach. In this exhaustive article, we’ll dive into the Binary Tree Preorder Traversal problem listed on LeetCode, analyze different approaches to solve it, and implement these solutions using Python.

Problem Statement

The Binary Tree Preorder Traversal problem is listed as problem number 144 on LeetCode. Here’s the problem statement:

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

Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [1]
Output: [1]

Understanding the Problem

In this problem, we are given the root of a binary tree and are required to return a list containing the values of the nodes as visited in preorder traversal. In preorder traversal, each node is visited in the following order: Node -> Left -> Right. This means we first visit the current node, then recursively visit the left subtree, and finally visit the right subtree.

Approach 1: Recursive Solution

One of the most intuitive solutions to this problem is to use recursion. We create a helper function that takes in a node and a list. If the node is not null, we add its value to the list and then recursively call the function for the left and right children.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root):
    def helper(node, result):
        if node:
            result.append(node.val)
            helper(node.left, result)
            helper(node.right, result)
    
    result = []
    helper(root, result)
    return result

This approach has a time complexity of O(n), where n is the number of nodes in the tree, as each node is visited once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.

Approach 2: Iterative Solution using Stack

An alternative to the recursive approach is to use iteration with the help of a stack. This method emulates the function call stack that you would have in a recursive approach.

In this approach, we start with the root node and keep adding the node’s value to the result list and pushing the right child followed by the left child to the stack (if they exist). We continue this process until the stack is empty.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root):
    if not root:
        return []
    
    stack, result = [root], []
    
    while stack:
        node = stack.pop()
        if node:
            result.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
    
    return result

This iterative approach also has a time complexity of O(n) and space complexity of O(h), similar to the recursive approach. However, this solution might be slightly more space-efficient in practice due to the overhead that recursive calls can have.

Conclusion

We explored two different approaches to solve the Binary Tree Preorder Traversal problem on LeetCode using Python: recursive and iterative. Both methods have their own advantages. Recursive solutions are generally easier to write and are more readable, but they can lead to stack overflow errors on very deep trees. Iterative solutions, on the other hand, may require more code but can sometimes be more efficient in terms of space.

Understanding tree traversals is crucial as they are often used as building blocks for more complex tree algorithms. When faced with tree-related problems in coding interviews or real-world applications, knowing various traversal techniques, such as preorder traversal, can often be the key to finding an elegant and efficient solution.