Print diagonal traversal of a binary tree

Posted by on Mar 31, 2024

Given a binary tree, assume that the left and right child of a node makes a 45 degree angle with the parent.

Print all diagonal elements in the binary tree that belong to the same line, see the example below for illustration:

Example 1: Print diagonal traversal of a binary tree

Input:

Output:

1,3,6
2,5,8,9
4,7


Solutions

Method 1: Using Map (Recursion)

We can perform diagonal traversal on a binary tree using a Map, the idea is to group the nodes diagonally and print the map in ascending order of "diagional-number (key)".

Each key in the map represents a diagonal in the binary tree, and its value maintains all nodes present in the diagonal.

Do a level-order traversal and pass current-diagonal-number, "0" for the root; right child will have same number while the left child will get "+1" of his parent.

Complexity
The time complexity of this solution is O(n) and space complexity is O(n) due to auxiliary Map.

Method 2: Using Queue

We can perform diagonal traversal on a binary tree using a Queue, the idea is to keep on printing right child and pushing left child to the queue.

Only when the element's left is available will we push it into the queue.

We'll process the node and then go to the right.

Complexity
The time complexity of this solution is O(n) and space complexity is O(n) due to auxiliary Queue.

Related


Print a Binary Tree in Vertical Order

Pre-order Tree Traversal - Iterative and Recursive

Level Order or Breadth First traversal of Binary Tree

Print Nodes in Top View of a Binary Tree

In-order Tree Traversal - Iterative and Recursive

Create a mirror tree from a given binary tree

Print the left view of a binary tree

Write a program to print height/depth of a Binary Tree

Find the diameter or width of a binary tree

Print/Traverse a Binary Tree in Zigzag Order