Vertical Traversal of a Binary tree

Question

Explore efficient vertical traversal of binary trees with our comprehensive guide. Learn essential algorithms and techniques for optimal tree traversal. Enhance your understanding of data structures and algorithms while mastering popular keywords like binary tree traversal, vertical order traversal, tree traversal algorithms, and more. Elevate your coding skills with insights and examples on navigating binary trees vertically. Start your journey to becoming a proficient programmer today!

Answer 1

Vertical Traversal of a Binary tree

Vertical Traversal of a Binary Tree involves traversing the tree vertically from top to bottom, considering horizontal distances. Nodes that are at the same horizontal distance are grouped together, and their values are printed in order. This traversal helps us visualize the structure of the binary tree based on the horizontal positions of nodes.

Let's break down the process step by step:

1. Understanding Vertical Traversal:

Vertical traversal involves assigning horizontal distances to nodes. The root is assigned a distance of 0, and as we move left, the distance decreases, and as we move right, the distance increases.

2. Data Structure:

We need a data structure to store nodes along with their horizontal distances. A map or a hash table is suitable for this purpose.

3. Algorithm:

• Start with the root node and horizontal distance 0.
• Traverse the tree using any traversal technique (e.g., inorder, preorder, or postorder).
• Keep track of the horizontal distance for each node.
• Store nodes in a map or hash table based on their horizontal distances.
• Print nodes in order of increasing horizontal distances.

Consider the below tree:

In the given tree, where 'a' serves as the root node, Hd (horizontal distance) is initialized to 0 for this node. Applying rules, since 'b' is the left child of node 'a,' Hd for 'b' is set to 0 minus 1 (0-1), resulting in Hd equal to -1. Node 'c' being the right child of 'a' follows rule number 3, assigning Hd to 0 plus 1 (0+1), making Hd of 'c' equal to 1.

Continuing, as 'd' is the left child of 'b,' Hd for 'd' is calculated as the Hd value of its parent minus one, thus Hd equals -1-1, giving -2. 'e,' the right child of 'b,' adheres to rule 3, with Hd being the Hd value of its parent plus one, resulting in -1 + 1, which is 0.

Similarly, 'f' being the left child of 'c' leads to Hd of 'f' being (1-1), resulting in zero. 'g' being the right child of 'c' causes Hd of 'g' to be (1+1), giving 2.

For 'h,' the left child of 'd,' Hd is calculated as (-2-1), yielding -3. 'i,' the right child of 'd,' has Hd equal to -1. For 'j,' the left child of 'e,' Hd is -1, and for 'k,' the right child of 'e,' Hd is 1.

Continuing with 'l,' the left child of 'g,' Hd of 'l' is (2-1), resulting in 1. Finally, 'm,' the right child of 'g,' has Hd of (2+1), which is 3.

The node with the minimum Hd value is 'h' at -3, and the node with the maximum Hd value is 'm' at 3. Nodes sharing the same Hd value exist in the same vertical line. Vertical lines are created for each unique Hd value, passing through the corresponding nodes.

Algorithm Steps for Vertical Traversal:

1. Enqueue the root.
2. Update Hd distance for the root as 0.
3. Add Hd as 0 in a hash table, with the root as the associated value.
4. Perform Dequeue operation and:
   • Check for left and right child nodes, updating Hd in the hash table.
   • Enqueue the left and right child nodes.

These steps are repeated until the traversal is complete, creating vertical lines based on Hd values.

Consider the below tree:

We will use two data structures such as Queue, and hash table to implement the vertical traversal,

• We first insert the node 'a' in a queue and update the horizontal distance value of node 'a' as 0. We will also add the H_d of node 'a' and the value in a hash table shown as below:

According to Step 4 specified in the algorithm, element 'a' is dequeued from the queue and update the hash table with Hd value of left and right child of node 'a' shown as below:

Once the hash table is updated, we will enqueue the left and right child of node 'a' in a queue shown as below:

Step 4 is in loop, and it will iterate till the queue does not become empty.

• Check whether the queue is empty or not. The queue is not empty, so dequeue the element 'b' from the queue, and check the left and the right child of 'b' node. Since the node 'b' has both left and right child so we will update the hash table with the Hd value of node 'd' and 'e' shown as below:

Once the hash table gets updated, enqueue the nodes 'd' and 'e' in a queue shown as below:

• Check whether the queue is empty or not. The queue is not empty so dequeue the element 'c' from the queue, and check the left and right child of 'c' node. Since the node 'c' has both left and right child so we will update the hash table with Hd values of node 'f' and 'g' shown as below:

Once the hash table gets updated, enqueue the nodes 'f' and 'g' in a queue shown as below:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'd' from the queue, and check the left and right child of node 'd'. Since the node 'd' has both left and right child so we will update the hash table with Hd values of 'h' and 'i' shown as below:

Once the hash table gets updated, enqueue the nodes 'h' and 'i' in a queue shown as below:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'e' from the queue, and check the left and right child of node 'e'. Since node 'e' does not have any left and right child so there will be no updation in the hash table:
• We will check again whether the queue is empty or not. The queue is not empty so dequeue the element 'f' from the queue, and check the left and right of node 'f'. Since the node 'f' has both left and right child, we will update the hash table with Hd values of 'j' and 'k'.

Once the hash table gets updated, enqueue the nodes 'j' and 'k' in a queue shown as below:

• We will check again whether the queue is empty or not. The queue is not empty so dequeue the element 'g' from the queue, and check the left and right of node 'l'. Since the node 'g' has the only right child, we will update the hash table with Hd values of 'l'.

Answer 2

Once the hash table gets updated, enqueue the node 'g' in a queue shown as below:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'h' from the queue, and check the left and right child of node 'h'. Since node 'h' does not have any left and right child so there will be no updation in the hash table:

• We will check again whether the queue is empty or not. The queue is not empty so dequeue the element 'i' from the queue, and check the left and right of node 'i'. Since the node 'i' has both left and right child so we will update the hash table with Hd values of 'm' and 'n'.

Once the hash table gets updated, enqueue the nodes 'm' and 'n' in a queue shown as below:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'j' from the queue, and check the left and right child of node 'j'. Since node 'j' does not have any left and right child so there will be no updation in the hash table:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'k' from the queue, and check the left and right child of node 'k'. Since node 'k' has both left and right child so we will update the hash table with Hd values of 'p' and 'q'.

Once the hash table gets updated, enqueue the nodes 'p' and 'q' in a queue shown as below:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'l' from the queue, and check the left and right child of node 'l'. Since node 'l' does not have any left and right child so there will be no updation in the hash table:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'm' from the queue, and check the left and right child of node 'm'. Since node 'm' does not have any left and right child so there will be no updation in the hash table:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'n' from the queue, and check the left and right child of node 'n'. Since node 'n' does not have any left and right child so there will be no updation in the hash table:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'p' from the queue, and check the left and right child of node 'p'. Since node 'p' does not have any left and right child so there will be no updation in the hash table:

• Check again whether the queue is empty or not. The queue is not empty so dequeue the element 'q' from the queue, and check the left and right child of node 'q'. Since node 'q' does not have any left and right child so there will be no updation in the hash table:

4. Example Code (in Python):

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

def vertical_traversal(root):
    # Initialize an empty dictionary to store nodes at each horizontal distance
    vertical_dict = {}

    # Helper function for recursive traversal
    def traverse(node, distance, vertical_dict):
        if node is not None:
            # Store the node in the dictionary based on its horizontal distance
            if distance in vertical_dict:
                vertical_dict[distance].append(node.val)
            else:
                vertical_dict[distance] = [node.val]

            # Recur for the left and right subtrees with updated distances
            traverse(node.left, distance - 1, vertical_dict)
            traverse(node.right, distance + 1, vertical_dict)

    # Start traversal from the root with distance 0
    traverse(root, 0, vertical_dict)

    # Print nodes in order of increasing horizontal distances
    for distance in sorted(vertical_dict.keys()):
        print(" ".join(map(str, vertical_dict[distance])))

# Example usage:
# Construct a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# Perform vertical traversal
vertical_traversal(root)
 

5. Example Output:

4
2
1 5 6
3
7
 

In this example, the nodes are printed vertically based on their horizontal distances. Nodes with the same distance are grouped together, and their values are printed in order.

Answer 3

FAQs on Vertical Traversal of a Binary tree

Q: What is vertical traversal of a binary tree?

A: Vertical traversal of a binary tree involves visiting the nodes of the tree in a vertical order. Nodes at the same horizontal distance from the root are visited together. Nodes to the left are visited before nodes to the right at the same horizontal distance.

Q: How to perform vertical traversal of a binary tree?

A: Here's an example code in Python using a simple binary tree structure:

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

def verticalTraversal(root):
    if not root:
        return []

    # Dictionary to store nodes at each vertical distance
    vertical_dict = {}

    # Queue to perform level order traversal
    queue = [(root, 0)]

    while queue:
        node, distance = queue.pop(0)

        # Update the dictionary
        if distance in vertical_dict:
            vertical_dict[distance].append(node.val)
        else:
            vertical_dict[distance] = [node.val]

        # Enqueue left child with a decreased distance
        if node.left:
            queue.append((node.left, distance - 1))

        # Enqueue right child with an increased distance
        if node.right:
            queue.append((node.right, distance + 1))

    # Sort the result based on vertical distance
    result = [vertical_dict[key] for key in sorted(vertical_dict)]
    return result

# Example usage:
# Constructing a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# Output: [[4], [2], [1, 5, 6], [3], [7]]
print(verticalTraversal(root))
 

Q: How to modify the code for printing the nodes in a top-down manner at each vertical distance?

A: You can modify the code to print the nodes in a top-down manner at each vertical distance by changing the order of appending nodes to the result. Here's the modified part of the code:

# Update the dictionary
if distance in vertical_dict:
    vertical_dict[distance].insert(0, node.val)  # Insert at the beginning for top-down order
else:
    vertical_dict[distance] = [node.val]
 

This modification ensures that nodes are inserted at the beginning of the list for each vertical distance, resulting in a top-down order.

Important Interview Questions and Answers on Vertical Traversal of a Binary tree

Q: Explain the concept of vertical traversal in a binary tree.

Vertical traversal in a binary tree involves printing nodes based on their vertical distance from the root. Nodes with the same vertical distance are printed in the same column. We can use a map or hash table to store nodes at each vertical distance, and then traverse the tree to populate this map.

Q: How do you implement vertical traversal of a binary tree?

We can implement vertical traversal using a map where the keys represent the horizontal distance and the values are lists of nodes at that distance. We perform a depth-first traversal of the tree, updating the map at each step.

Q: Provide an example code for vertical traversal of a binary tree.

Here is the code.

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

def vertical_traversal(root):
    if not root:
        return []

    # Dictionary to store nodes at each vertical distance
    vertical_map = {}

    # Helper function for DFS traversal
    def dfs(node, distance):
        if not node:
            return

        # Update the vertical_map
        if distance in vertical_map:
            vertical_map[distance].append(node.val)
        else:
            vertical_map[distance] = [node.val]

        # Traverse left and right
        dfs(node.left, distance - 1)
        dfs(node.right, distance + 1)

    # Start DFS traversal from the root with distance 0
    dfs(root, 0)

    # Sort the keys to print nodes in order
    sorted_keys = sorted(vertical_map.keys())

    # Print nodes in each vertical distance
    for key in sorted_keys:
        print(" ".join(map(str, vertical_map[key])))

# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

print("Vertical Traversal:")
vertical_traversal(root)
 

Q: What is the time complexity of the vertical traversal algorithm?

The time complexity of the vertical traversal algorithm is O(n log n), where n is the number of nodes in the binary tree. The log n factor comes from the sorting of keys in the vertical_map.