Print vertical Traversal of binary tree

In this article, we will address the problem of printing the vertical traversal of a binary tree. Vertical traversal involves printing the nodes of the tree column by column, where columns are determined by horizontal distances from the root. We will explore how to implement this traversal in Java and print the nodes in each column.

Problem Statement

Given a binary tree, we want to print its vertical traversal. Vertical traversal means printing the nodes of the tree column by column, where columns are determined by horizontal distances from the root. Columns to the left of the root have negative distances, the root column has a distance of 0, and columns to the right of the root have positive distances.

Example

Let's consider a binary tree as an example:

The vertical traversal of this tree is as follows:

3
2 9
10 6 1
4 7
5 11

Each row represents a column in the tree, and the nodes in each column are printed from top to bottom.

Idea to Solve the Problem

To print the vertical traversal of a binary tree, we can use a level-order traversal approach along with a queue. We will assign horizontal distances to each node and use a HashMap to group nodes by their distances. By processing the nodes level by level, we can ensure that nodes in the same column are printed together.

Pseudocode

Here is the pseudocode for solving the problem:

function verticalTraversal():
    if root is null:
        return
    Create an empty HashMap record
    Create an empty queue q
    Add the root node to q with distance 0
    while q is not empty:
        node = dequeue from q
        distance = node's distance
        if distance not in record:
            record[distance] = empty list
        record[distance].add(node.data)
        if node has left child:
            enqueue left child with distance - 1 to q
        if node has right child:
            enqueue right child with distance + 1 to q
    Find the minimum and maximum distances in record
    for each distance from minimum to maximum:
        print all nodes at that distance in record

Algorithm Explanation

1. Initialize an empty HashMap called record to store nodes grouped by their horizontal distances.
2. Create an empty queue q.
3. Add the root node to q with a distance of 0.
4. Perform a level-order traversal using q:
   • Dequeue a node from q.
   • Get the distance of the dequeued node.
   • If the distance is not in record, create an empty list for that distance in record.
   • Add the data of the dequeued node to the list associated with its distance in record.
   • Enqueue the left child of the node with a distance decremented by 1 if it exists.
   • Enqueue the right child of the node with a distance incremented by 1 if it exists.
5. Find the minimum and maximum distances in record.
6. Iterate through distances from the minimum to the maximum and print all nodes at each distance.

Code Solution

1) Print vertical order of binary tree in java 2) Print vertical order of binary tree in c++ 3) Print vertical order of binary tree in c# 4) Print vertical order of binary tree in php 5) Print vertical order of binary tree in node js 6) Print vertical order of binary tree in python 7) Print vertical order of binary tree in ruby 8) Print vertical order of binary tree in scala 9) Print vertical order of binary tree in swift 10) Print vertical order of binary tree in kotlin 11) Print vertical order of binary tree in golang 12) Print vertical order of binary tree in vb.net

Time Complexity of the Code

The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the level-order traversal, and HashMap operations take constant time.