Binary Tree Preorder Traversal

Problem: Binary Tree Preorder Traversal

We use the stack to implement depth-first tree in order to get pre-order traversal. To pop left sub-tree first, we need to push right subtree first into the stack.

Code in Python:

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res, stack = [], []
        stack.append(root)
        while True:
            if not stack or not stack[-1]:
                break
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res