Lecture 181:-Vertical Order Traversal

Vertical order traversal of a binary tree involves printing the nodes of the tree in vertical order based on their horizontal distance from the root. Nodes at the same horizontal distance are printed on the same vertical line.

Here's a Python implementation of the vertical order traversal of a binary tree:

pythonCopy code

from collections import defaultdict, deque class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def vertical_order_traversal(root): if root is None: return # Dictionary to store nodes at each horizontal distance vertical_order = defaultdict(list) # Queue for BFS traversal queue = deque([(root, 0)]) while queue: node, distance = queue.popleft() vertical_order[distance].append(node.data) if node.left: queue.append((node.left, distance - 1)) if node.right: queue.append((node.right, distance + 1)) # Print nodes in vertical order for distance in sorted(vertical_order): print(" ".join(map(str, vertical_order[distance]))) # Example usage root = TreeNode(10) root.left = TreeNode(7) root.right = TreeNode(4) root.left.left = TreeNode(3) root.left.right = TreeNode(11) root.right.left = TreeNode(14) root.right.right = TreeNode(6) print("Vertical Order Traversal:") vertical_order_traversal(root)

In this example, the TreeNode class represents nodes of the binary tree. The vertical_order_traversal function performs the vertical order traversal of the binary tree using a breadth-first search (BFS) approach. It uses a dictionary vertical_order to store nodes at each horizontal distance from the root. The BFS traversal is done using a queue, where each element in the queue is a tuple containing the node and its distance from the root.

After completing the traversal, the nodes are printed in vertical order based on their horizontal distance.

Keep in mind that vertical order traversal is a specific type of tree traversal and might not be as commonly used as other traversal methods. However, it can be useful in certain scenarios, such as when you need to display nodes of a binary tree in a different order for visualization purposes.