Posted on by Kalkicode
Code Binary Tree

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:

Vertical traversal of binary tree

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

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.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment