Binary Tree Traversal — Leetcode 94, 144, 145

Difficulty: Easy; Category: Tree

There are three types of DFS traversal:
> Preorder: Root, Left, Right
> Inorder: Left, Root, Right
> Postorder: Left, Right, Root

As long as you can remember how the position of the root is placed related to these three order, you can easily solve the problems below.

LeetCode 94 — Binary Tree Inorder Traversal

Inorder traversal: Left, Root, Right

Binary Tree Inorder Traversal - LeetCode

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
            
        dfs(root)
        return result

LeetCode 144 — Binary Tree Preorder Traversal

Preorder traversal: Root, Left, Right

Binary Tree Preorder Traversal - LeetCode

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        
        def dfs(node):
            if not node:
                return
            result.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return result

LeetCode 145— Binary Tree Postorder Traversal

Postorder traversal: Left, Right, Root

Binary Tree Postorder Traversal - LeetCode

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            result.append(node.val)
        dfs(root)
        return result

Here introduce the difference between BFS Traversal and DFS Traversal with concepts and example codes, check this out:
Binary Tree Traversal — Data Structures and Algorithms Note