HomeAbout

Iterative traversal

BFS

In pseudo-code:

nodes_to_visit = [root];

while(nodes_to_visit.length != 0) {
  // .first() removes and returns the first element in the list
  // same as .shift() in other languages
  currentnode = nodes_to_visit.first();
  // push children to the end of the list, evaluate from left-most element, each left-most element is in the same level (upper level node), each lower-level nodes of an upper-level node gets pushed to the end of the list
  nodes_to_visit.append( currentnode.children );
  //do something
}

Python:

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

def bfs(root):
    if not root:
        return

    queue = [root]  # Initialize queue with the root node

    while queue:
        current_node = queue.pop(0)  # Dequeue the node (FIFO)
        print(current_node.value, end=" ")

        # Enqueue the left and right children (if any)
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

bfs(root) # 1 2 3 4 5

DFS

In pseudo-code:

nodes_to_visit = [root];

while(nodes_to_visit.length != 0) {
  // .first() removes and returns the first element in the list
  // same as .shift() in other languages
  currentnode = nodes_to_visit.first();
  // push the child to the beginning of the list, returning children in left-to-right order
  nodes_to_visit.prepend( currentnode.children );
  // do something with the currentnode
}

Python:

Pre-order

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

def dfs_preorder(root):
    if root is None:
        return

    nodes_to_visit = [root]

    while nodes_to_visit:
        current_node = nodes_to_visit.pop()  # pop from the end (LIFO)
        print(current_node.value, end=" ")

        # In pre-order, visit right child first so left child is processed first.
        if current_node.right:
            nodes_to_visit.append(current_node.right)
        if current_node.left:
            nodes_to_visit.append(current_node.left)

# Example tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Perform DFS pre-order traversal
dfs_preorder(root) # 1 2 4 5 3

In-order

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

def dfs_inorder(root):
    nodes_to_visit = []
    current_node = root

    while current_node or nodes_to_visit:
        # Traverse the left subtree, push all the left children onto the stack
        while current_node:
            nodes_to_visit.append(current_node)
            current_node = current_node.left

        # Now, pop the node from the stack, visit it, and move to the right subtree
        current_node = nodes_to_visit.pop()
        print(current_node.value, end=" ")

        # Move to the right child
        current_node = current_node.right

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Perform DFS in-order traversal
dfs_inorder(root) # 4 2 5 1 3

Post-order

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

def dfs_postorder(root):
    if not root:
        return

    stack = []
    output = []

    # Push the root node onto the stack
    stack.append(root)

    while stack:
        current_node = stack.pop()
        output.append(current_node.value)

        # Push the left child and right child onto the stack
        # Push left first, because we want to process right before left in post-order
        if current_node.left:
            stack.append(current_node.left)
        if current_node.right:
            stack.append(current_node.right)

    # Reverse the output list to get the post-order
    output.reverse()

    print("".join(map(str, output)))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

dfs_postorder(root) # 4 5 2 3 1

What is output list for?

  • In post-order traversal, we can't visit the node right away because we need to ensure that both the left and right children are processed first.
  • The output list stores the nodes in root-right-left order (the reverse of the desired post-order).

After traversing the entire tree and collecting nodes in this order, we reverse the list to get the correct post-order (left-right-root).

AboutContact