DFS Preorder, Inorder, Postorder and BFS¶

Preorder, Inorder and Postorder are different DFS exploration strategies¶

Here is a visualisation of Binary Trees generated using DFS Preorder, DFS Inorder, DFS Postorder and BFS¶

Implementation of Leetcode algorithms¶

Construct from Preorder Traversal¶

In [ ]:
def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    def helper(root):
        if not root:
            return([])
        return([root.val] + helper(root.left) + helper(root.right)) # val, left, right
    return(helper(root))

Construct from Inorder Traversal¶

In [ ]:
def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    def helper(root):
        if not root:
            return([])
        return(helper(root.left) + [root.val] + helper(root.right))  # left, val, right
    return(helper(root))

Construct from Postorder Traversal¶

In [ ]:
def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    def helper(root):
        if not root:
            return([])
        return(helper(root.left) + helper(root.right) + [root.val]) # left, right, val
    return(helper(root))