Tree Traversals#

Welcome to Day 16 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deep into various tree traversal techniques, exploring both recursive and iterative approaches. Tree traversals are fundamental operations for processing tree-based data structures and are crucial for solving many algorithmic problems.

Types of Tree Traversals#

There are two main categories of tree traversals:

1. Depth-First Search (DFS)

   • Inorder Traversal
   • Preorder Traversal
   • Postorder Traversal

2. Breadth-First Search (BFS)

   • Level Order Traversal

Let’s explore each of these in detail.

Depth-First Search (DFS) Traversals#

1. Inorder Traversal (Left, Root, Right)#

Inorder traversal visits the left subtree, then the root, and finally the right subtree.

Recursive Approach:#

1def inorder_recursive(root):
2    if root:
3        inorder_recursive(root.left)
4        print(root.val, end=" ")
5        inorder_recursive(root.right)

Iterative Approach:#

 1def inorder_iterative(root):
 2    stack = []
 3    current = root
 4    while stack or current:
 5        while current:
 6            stack.append(current)
 7            current = current.left
 8        current = stack.pop()
 9        print(current.val, end=" ")
10        current = current.right

2. Preorder Traversal (Root, Left, Right)#

Preorder traversal visits the root, then the left subtree, and finally the right subtree.

Recursive Approach:#

1def preorder_recursive(root):
2    if root:
3        print(root.val, end=" ")
4        preorder_recursive(root.left)
5        preorder_recursive(root.right)

Iterative Approach:#

 1def preorder_iterative(root):
 2    if not root:
 3        return
 4    stack = [root]
 5    while stack:
 6        node = stack.pop()
 7        print(node.val, end=" ")
 8        if node.right:
 9            stack.append(node.right)
10        if node.left:
11            stack.append(node.left)

3. Postorder Traversal (Left, Right, Root)#

Postorder traversal visits the left subtree, then the right subtree, and finally the root.

Recursive Approach:#

1def postorder_recursive(root):
2    if root:
3        postorder_recursive(root.left)
4        postorder_recursive(root.right)
5        print(root.val, end=" ")

Iterative Approach:#

 1def postorder_iterative(root):
 2    if not root:
 3        return
 4    stack1, stack2 = [root], []
 5    while stack1:
 6        node = stack1.pop()
 7        stack2.append(node)
 8        if node.left:
 9            stack1.append(node.left)
10        if node.right:
11            stack1.append(node.right)
12    while stack2:
13        print(stack2.pop().val, end=" ")

Breadth-First Search (BFS) Traversal#

Level Order Traversal#

Level order traversal visits nodes level by level from left to right.

 1from collections import deque
 2
 3def level_order_traversal(root):
 4    if not root:
 5        return
 6    queue = deque([root])
 7    while queue:
 8        level_size = len(queue)
 9        for _ in range(level_size):
10            node = queue.popleft()
11            print(node.val, end=" ")
12            if node.left:
13                queue.append(node.left)
14            if node.right:
15                queue.append(node.right)
16        print()  # New line for each level

Time and Space Complexity#

For all traversals:

• Time Complexity: O(n), where n is the number of nodes in the tree
• Space Complexity:
  • Recursive: O(h) in the worst case, where h is the height of the tree
  • Iterative: O(n) in the worst case for a skewed tree

Applications of Tree Traversals#

1. Inorder Traversal:

   • Used to get nodes of BST in non-decreasing order
   • Used in expression tree evaluation

2. Preorder Traversal:

   • Used to create a copy of the tree
   • Used to get prefix expression on an expression tree

3. Postorder Traversal:

   • Used to delete the tree
   • Used to get postfix expression of an expression tree

4. Level Order Traversal:

   • Used in level order problems
   • Used in finding the minimum depth of a binary tree

Advanced Traversal Techniques#

1. Morris Traversal#

Morris Traversal allows us to traverse the tree without using stack or recursion. It has O(1) space complexity.

 1def morris_inorder(root):
 2    current = root
 3    while current:
 4        if not current.left:
 5            print(current.val, end=" ")
 6            current = current.right
 7        else:
 8            predecessor = current.left
 9            while predecessor.right and predecessor.right != current:
10                predecessor = predecessor.right
11            
12            if not predecessor.right:
13                predecessor.right = current
14                current = current.left
15            else:
16                predecessor.right = None
17                print(current.val, end=" ")
18                current = current.right

2. Threaded Binary Tree Traversal#

A threaded binary tree uses the null pointers in leaf nodes to create threads to other nodes, allowing for more efficient traversal without using a stack or recursion.

Exercise#

1. Implement a function to perform zigzag level order traversal of a binary tree.
2. Create a method to find the vertical order traversal of a binary tree.
3. Implement a function to serialize and deserialize a binary tree.

Summary#

Today, we explored various tree traversal techniques, including depth-first (inorder, preorder, postorder) and breadth-first (level order) approaches. We implemented both recursive and iterative versions of these traversals and discussed their applications and complexities.

Understanding these traversal methods is crucial for solving a wide range of tree-based problems and forms the foundation for more advanced tree algorithms. As we progress through this challenge, you’ll find these traversal techniques invaluable in tackling complex tree-related problems.

Tomorrow, we’ll dive into heaps and priority queues, building upon our knowledge of trees to explore these specialized data structures. Stay tuned!

Solution#

 1from collections import deque
 2
 3def zigzag_level_order(root):
 4    if not root:
 5        return []
 6    result = []
 7    queue = deque([root])
 8    left_to_right = True
 9    while queue:
10        level = deque()
11        for _ in range(len(queue)):
12            node = queue.popleft()
13            if left_to_right:
14                level.append(node.val)
15            else:
16                level.appendleft(node.val)
17            if node.left:
18                queue.append(node.left)
19            if node.right:
20                queue.append(node.right)
21        result.append(list(level))
22        left_to_right = not left_to_right
23    return result