Preorder Traversal

Return the preorder traversal of a binary tree as a list of node values.

binary-tree traversal recursion dfs

Implement the function `preorder_traversal(root)` that takes the root node of a binary tree and returns a list of its node values in preorder order (root, left, right).

Each node is an instance of the class `TreeNode` provided below. You must also include this class definition in your solution.

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

For an empty tree (root is None), return an empty list.

You may solve this iteratively or recursively.

Constraints

The number of nodes in the tree is in the range [0, 100]. Node values are integers. Your solution should run in O(n) time where n is the number of nodes.

Example

>>> # Example 1:
>>> root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
>>> preorder_traversal(root)
[1, 2, 3]
>>> # Example 2:
>>> preorder_traversal(None)
[]
>>> # Example 3:
>>> root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
>>> preorder_traversal(root)
[1, 2, 4, 5, 3, 6, 7]

10 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Preorder means visit the root first, then traverse the left subtree, then the right subtree.

A recursive approach: base case if root is None return []. Then combine [root.val] with results from left and right.

For an iterative method, use a stack. Pop a node, add its value, then push right child first so left is processed first.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.