Traverse

Traverse Binary Tree # 

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def visit(self):
        print(self.val)

BFS traversal #

Level-order traversal #

DFS traversal #

DFS traversal of a binary tree can be used to solve the following problems.

Maximum width, minimum depth and diameter of a binary tree
Binary tree iterator
Convert a binary tree into a mirror tree
Find k smallest/largest elements of a binary search tree
Boundary traversal of binary tree
Lowest common ancestor of two nodes in a binary tree
Construct a binary tree from pre-order and in-order traversal

Pre-order traversal #

Parent -> Left child -> Right child

Can be used to create a copy of the tree.

def preorder_recursive(node):
    if node is None:
        return
    node.visit()
    preorder_recursive(node.left)
    preorder_recursive(node.right)

# Since parents are visited prior to children, we can push to and pop from stack
# in a loop as we go. The right child needs to pushed before left child so that
# left child is popped first.
def preorder_iterative(node):
    if node is None:
        return 
    stack = []
    stack.append(node)
    while stack:
        node = stack.pop()
        node.visit()
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Reverse pre-order traversal #

Parent -> Right child -> Left child

def reverse_preorder_recursive(node):
    if node is None:
        return
    node.visit()
    reverse_preorder_recursive(node.right)
    reverse_preorder_recursive(node.left)

# Since parents are visited prior to children, we can push to and pop from stack
# in a loop as we go. The left child needs to pushed before right child so that
# right child is popped first.
def reverse_preorder_iterative(node):
    if node is None:
        return
    stack = []
    stack.append(node)

    while stack:
        node = stack.pop()
        node.visit()
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

In-order traversal #

Left child -> Parent -> Right child

Traversing a binary search tree (BST) in-order will visit the nodes in sorted order (ascending). Other applications include construction of BST, creating balanced BST from sorted array, determining if a tree is balanced, and finding k-smallest elements in a BST.

def inorder_recursive(node):
    if node is None:
        return
    inorder_recursive(node.left)
    node.visit()
    inorder_recursive(node.right)

# Since left child has to be visited first, we need to push left children to the
# stack until we reach a leaf node. We then start popping the nodes and after 
# visiting the popped nodes, push its right node, if it exist. If the right node 
# contains a subtree (could be even a complete subtree), this subtree will be 
# visited in-order as well.
def inorder_ietrative(node):
   stack = []
   while stack or node:
    if node:
        stack.append(node)
        node = node.left
    else:
        node = stack.pop()
        node.visit()
        node = node.right

Reverse in-order traversal #

Right child -> Parent -> Left child

Traversing a binary search tree (BST) using reverse in-order method will visit the nodes in sorted order (descending). That means, it can be used to get K-largest elements in a BST as well.

def reverse_inorder_recusrive(node):
    if node is None:
        return
    reverse_inorder_recusrive(node.right)
    node.visit()
    reverse_inorder_recusrive(node.left)

# Since right child has to be visited first, we need to push right children to \
# the stack until we reach a leaf node. We then start popping the nodes and 
# after visiting the popped nodes, push its left node, if it exist. If the 
# left node contains a subtree (could be even a complete subtree), this subtree
# will be  visited in-order as well.
def reverse_inorder_iterative(node):
    stack = []
    while stack or node:
        if node:
            stack.append(node)
            node = node.right
        else:
            node = stack.pop()
            node.visit()
            node = node.left

Post-order traversal #

Left child -> Right child -> Parent

Can be used to delete tree from leaf to root.

def postorder_recursive(node):
    if node is None:
        return
    postorder_recursive(node.left)
    postorder_recursive(node.right)
    node.visit()

def postorder_iterative(node):
    stack = []
    last_seen = None
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek_node = stack[-1]
            if peek_node.right and peek_node.right != last_seen:
                node = peek_node.right
            else:
                peek_node.visit()
                last_seen = stack.pop()

Reverse post-order traversal #

Right child -> Left child -> Parent

def reverse_postorder_recursive(node):
    if node is None:
        return
    reverse_postorder_recursive(node.right)
    reverse_postorder_recursive(node.left)
    node.visit()

def reverse_postorder_iterative(node):
    stack = []
    last_seen_node = None

    while stack or node:
        if node:
            stack.append(node)
            node = node.right
        else:
            peek_node = stack[-1]
            if peek_node.left and peek_node.left != last_seen_node:
                node = peek_node.left
            else:
                peek_node.visit()
                last_seen_node = stack.pop()

Test Code #

graph TB; A((1))-->B((2)) A-->C((3)); B-->E((4)) B-->F((5)) C-->H((6)) C-->I((7)) E-->M((null)) E-->J((8)) J-->K((9)) J-->L((10)) 

if __name__ == '__main__':
    root = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    root.left = n2
    root.right = n3
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n2.left = n4
    n2.right = n5
    n6 = TreeNode(6)
    n7 = TreeNode(7)
    n3.left = n6
    n3.right = n7
    n8 = TreeNode(8)
    n4.right = n8
    n9 = TreeNode(9)
    n10 = TreeNode(10)
    n8.left = n9
    n8.right = n10

    
    print("In-order Recursive")
    inorder_recursive(root)
    print("In-order Iterarive")
    inorder_ietrative(root)
    print("Reverse In-order Recursive")
    reverse_inorder_recusrive(root)
    print("Reverse In-order Iterative")
    reverse_inorder_iterative(root)

    print("-------------------------")
    
    print("Pre-order recursive")
    preorder_recursive(root)
    print("Pre-order Iterative")
    preorder_iterative(root)
    print("Reverse Pre-order recursive")
    reverse_preorder_recursive(root)
    print("Reverse Pre-order Iterative")
    reverse_preorder_iterative(root)

    print("-------------------------")
    
    print("Post-order recursive")
    postorder_recursive(root)
    print("Post-order Iterative")
    postorder_iterative(root)
    print("Reverse Post-order recursive")
    reverse_postorder_recursive(root)
    print("Reverse Post-order Iterative")
    reverse_postorder_iterative(root)

Resources #

A good resource to understand different tree traversal algorithms is Wikipedia. Also check EnjoyAlgorithms, StackOverflow and Testbook.