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
- Initialize an empty
HashMap
calledrecord
to store nodes grouped by their horizontal distances. - Create an empty queue
q
. - Add the root node to
q
with a distance of 0. - 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 inrecord
. - 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.
- Dequeue a node from
- Find the minimum and maximum distances in
record
. - 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.
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