Binary Tree Preorder Traversal | LeetCode 144 | Python | Solution

Click here to see the problem on LeetCode.

The problem description is pretty straightforward. We have to return all the nodes’ values following the preorder traversal algorithm.

I can assume that you have a basic understanding of Tree data structure.

Mainly, there are four types of traversing algorithms in Binary Tree. Preorder traversal is one of them.

These algorithms follow different rules to visit nodes’ in a Binary Tree. In this case (preorder), it follows the rule ‘root->left->right‘ when visiting a Binary Tree.

We can solve this problem in both ways, iterative and recursive.

Let’s see both solutions.

Iterative

class Solution:
    def preorderTraversal(self, root: 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

Recursive

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:

        result = []
        self.helper(root, result)
        return result
    
    def helper(self, root, result):
        
        if root is None:
            return
        
        result.append(root.val)
        self.helper(root.left, result)
        self.helper(root.right, result)