Binary Tree Preorder Traversal - Leetcode Solution

Problem Statement:

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

Preorder traversal of a binary tree:

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

Example:

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

Solution:

The first approach that comes to mind is to simply use recursion. We can define a helper function that takes in a node and traverses its children. We can then iterate through the tree, calling this helper function on each node.

Algorithm:

1. Initialize an empty list called output.

2. Define a helper function called traverse that takes in a node, and the output list.

   a. If the node is not None, add its value to the output list. b. Recursively call the traverse function on the left child of the node. c. Recursively call the traverse function on the right child of the node.

3. Call the traverse function on the root node to populate the output list.

4. Return the output list.

Time Complexity: O(n) Space Complexity: O(h), where h is the height of the binary tree.

Code:

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: """ :type root: TreeNode :rtype: List[int] """ output = []

    def traverse(node, output):
        if node is None:
            return
        
        output.append(node.val)
        
        traverse(node.left, output)
        traverse(node.right, output)
    
    traverse(root, output)
    
    return output

1