067.md

144. Binary Tree Preorder Traversal

Difficulty: 🟢 Easy

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

Examples:

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

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

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• 100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Solutions

O(n) solution

Python3

# 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
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

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

        return result

The given solution provides an iterative approach to perform a preorder traversal of a binary tree.

Here is a step-by-step overview of the solution:

1. Check if the root is None. If it is, return an empty list as there are no nodes to traverse.
2. Initialize an empty list result to store the preorder traversal and a stack with the root node.
3. Enter a loop that continues until the stack is not empty:
   • Pop a node from the stack.
   • Append the value of the node to the result.
   • If the node has a right child, push the right child to the stack.
   • If the node has a left child, push the left child to the stack.
4. Return the result, which contains the preorder traversal of the binary tree.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the binary tree. We visit each node once.

The space complexity is O(h), where h is the height of the binary tree. In the worst case, the stack can contain all nodes along the path from the root to the leftmost leaf.

Summary

The given solution provides an iterative approach to perform a preorder traversal of a binary tree. It uses a stack to keep track of the nodes to visit and appends the node values to the result list in preorder. The solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes and h is the height of the binary tree.

NB: If you want to get community points please suggest solutions in other languages as merge requests.