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
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.