Problem statement

https://leetcode.com/problems/binary-tree-preorder-traversal/

Solution

Recursive solution is trivial. Alternative is to apply classical dfs, which can be implemented using stack. We add element to output when we remove it from stack.

Complexity

Time complexity is O(n), space is O(h).

Code

class Solution:
    def preorderTraversal(self, root):
        if not root: return []
        stack, out = [root], []
        while stack:
            cur = stack.pop()
            out.append(cur.val)
            for child in filter(None, [cur.right, cur.left]):
                stack += [child]
        return out