Diagonal Traversal of Binary Tree
In this article, we will tackle the problem of performing diagonal traversal of a binary tree. Diagonal traversal involves visiting nodes of the binary tree in a diagonal pattern, starting from the top-left and moving towards the bottom-right. We will explore how to implement this traversal in Java and print the nodes in the diagonal order.

Problem Statement
Given a binary tree, we want to perform a diagonal traversal of the tree. Diagonal traversal means visiting nodes in a diagonal pattern from the top-left to the bottom-right, where nodes with the same diagonal distance are visited together. For each diagonal, we will print the nodes from top to bottom.
Example
Let's consider a binary tree as an example:
10
/ \
/ \
2 4
/ / \
3 6 \
/ \ \
1 7 5
/ /
9 3
The diagonal traversal of this tree results in the following output:
10 4 5
2 6 7 3
3 1 9
Nodes with the same diagonal distance are visited together, and we move from the top-left to the bottom-right diagonally.
Idea to Solve the Problem
To perform diagonal traversal of the binary tree, we can use a recursive approach. We will keep track of the diagonal distance of each node from the root and store nodes with the same diagonal distance in a data structure, such as an ArrayList, associated with that distance. We will start from the root with a diagonal distance of 0, and as we move to the left child, we increment the diagonal distance by 1, and when we move to the right child, we keep the same diagonal distance. We will use a HashMap to store the nodes at each diagonal distance.
Pseudocode
Here is the pseudocode for solving the problem:
function getDiagonalView(node, distance, record):
if node is not null:
if distance not in record:
record[distance] = new ArrayList()
record[distance].add(node.data)
getDiagonalView(node.left, distance + 1, record)
getDiagonalView(node.right, distance, record)
function diagonalView():
record = empty HashMap
getDiagonalView(root, 0, record)
distance = 0
while distance in record:
for node in record[distance]:
print node
increment distance by 1
Algorithm Explanation
- Initialize an empty
HashMap
calledrecord
to store nodes at each diagonal distance. - Call the
getDiagonalView
function starting from the root node with an initial distance of 0. - In the
getDiagonalView
function:- If the current node is not null, check if the current distance is already in
record
. If not, create a new ArrayList for that distance. - Add the node's data to the ArrayList associated with the current distance.
- Recursively call the function for the left child with an incremented distance (moving diagonally down to the left).
- Recursively call the function for the right child with the same distance (moving diagonally down to the right).
- If the current node is not null, check if the current distance is already in
- After the traversal is complete, iterate through the
record
map, starting from distance 0, and print the nodes in each diagonal distance. - Increment the distance by 1 in each iteration until all diagonal distances are printed.
Code Solution
-
1) Diagonal traversal of binary tree in java
2) Diagonal traversal of binary tree in c++
3) Diagonal traversal of binary tree in c#
4) Diagonal traversal of binary tree in vb.net
5) Diagonal traversal of binary tree in php
6) Diagonal traversal of binary tree in node js
7) Diagonal traversal of binary tree in typescript
8) Diagonal traversal of binary tree in python
9) Diagonal traversal of binary tree in ruby
10) Diagonal traversal of binary tree in scala
11) Diagonal traversal of binary tree in swift
12) Diagonal traversal of binary tree in kotlin
13) Diagonal traversal of binary tree in golang
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 depth-first traversal, and the 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