algoadvance

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

A preorder traversal of a binary tree is a type of depth-first traversal that visits nodes in the following order:

1. Visit the root node.
2. Traverse the left subtree in a preorder manner.
3. Traverse the right subtree in a preorder manner.

Example:

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

Clarifying Questions

1. How should we handle an empty tree?
   • If the tree is empty, we should return an empty list.
2. What data structure is the input provided in?
   • The input is provided as a TreeNode class where each node has a value, and pointers to the left and right child nodes.
3. Is there any need to handle invalid input (like strings or other data types)?
   • No, you can assume the input will always be a valid binary tree or None.

Strategy

To perform a preorder traversal, we can use either an iterative approach or a recursive approach.

Recursive Approach:

1. Define a helper function that takes a node and the current traversal result list.
2. If the current node is None, return.
3. Add the value of the current node to the result list.
4. Recursively call the helper function on the left subtree.
5. Recursively call the helper function on the right subtree.

Iterative Approach:

1. Use a stack to keep track of nodes to visit.
2. Initialize the stack with the root node.
3. While the stack is not empty:
   • Pop a node from the stack.
   • Add its value to the result list.
   • Push the right child onto the stack (if it exists).
   • Push the left child onto the stack (if it exists).

We’ll go with the iterative approach for this solution.

Code

# 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

def preorderTraversal(root: TreeNode):
    if root is None:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right child first so that left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once.

• Space Complexity: O(n) in the worst case for the stack if the tree is completely unbalanced (resembling a linked list). In the average case (balanced tree), the space complexity will be O(log n). The result list will also take O(n) space.

This solution efficiently handles the preorder traversal of a binary tree using an iterative approach.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?