tree traversals

DFS traversals

  • Recurrsive implementation of the tree dfs traversals are pretty straightforwardly easy.
  • With a hashset, the iterative implementation can be very easy, but it need at least extra O(h) space for the hash.
  • Otherwise, the iterative version of the three dfs traversals can be quite different and nasty.
def inorder(node):
    if node.left: inorder(node.left)
    if node.right: inorder(node.right)

def postorder(node):
    if node.left: postorder(node.left)
    if node.right: postorder(node.right)

def preorder(node):
    if node.left: preorder(node.left)
    if node.right: preorder(node.right)

def tree_dfs_iterative(root):
    stack = [root]
    visited = set()
    while stack:
        node = stack.pop()
        if not node: continue
        if node in visited: print(node.val); return
        # stack.extend([node.right, node, node.left])  # inorder
        # stack.extend([node, node.right, node.left])  # postorder
        stack.extend([node.right, node.left, node])  # preorder

def inorder_iterative(root):
    node, stack = root, []
    while stack or node:
        while node:
            node = node.left
        node = stack.pop()
        node = node.right

def preorder_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if not node: continue

def postorder_iterative(root):
    stack = [(root, 0)]
    while stack:
        node, post = stack.pop()
        if post: print(node.val); continue
        stack.append((node, 1))
        if node.right: stack.append((node.right, 0))
        if node.left: stack.append((node.left, 0))

BFS traversal

  • BFS traversal with queue is quite straightforward. ```python def tree_bfs_iterative(root): queue = deque([root]) while queue: node = queue.popleft() if not node: continue print(node.val) queue.extend([node.left, node.right])

def tree_bfs_iterative(root): level = [root]
i = 0 while level: next_level = [] for node in level: print(node.val) if node.left: next_level.append(node.left) if node.right: next_level.append(node.right) level = next_level ```

Augment the tree node

  • Can be useful if we keep track of various information on node:
    • size / min / max of the subtree rooted at node
    • pointer to parent node
    • height / depth of the node