Diagonal Traversal of a Binary Tree - Iterative - Visualization
Visualization Player
Problem Statement❯
Examples❯
| Input Tree | Diagonal Traversal Output | Description |
|---|---|---|
| [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
|
[[8, 10, 14], [3, 6, 7, 13], [1, 4]] | Standard tree with multiple diagonals including both left and right subtrees |
| [1]
|
[[1]] | Single-node tree with only the root |
| [] | [] | Empty binary tree with no nodes |
| [1, 2, null, 3, null, 4]
|
[[1], [2], [3], [4]] | Left-skewed binary tree with only left children |
| [1, null, 2, null, 3, null, 4]
|
[[1, 2, 3, 4]] | Right-skewed binary tree, all nodes fall in the same diagonal |
| [10, 20, 30, 40, null, null, 50]
|
[[10, 30, 50], [20], [40]] | Tree with mixed left and right children forming three diagonals |
Solution❯
Understanding the Problem
We are given a binary tree and asked to perform a diagonal traversal. In a diagonal traversal, nodes that lie on the same diagonal from top-right to bottom-left are grouped together.
The idea is that if you start at the root and keep moving right, all the nodes you encounter are on the same diagonal. If a node has a left child, it belongs to the next diagonal and should be processed later.
We want to return a single list of nodes as they appear in a diagonal-wise order, starting from the top-rightmost diagonal.
Step-by-Step Solution with Example
Step 1: Consider the given binary tree
8
/ 3 10
/ 1 6 14
/ /
4 7 13
We'll traverse this tree diagonally.
Step 2: Use a queue to help us process nodes
We use a queue to keep track of the left children we encounter (they belong to the next diagonal).
We start by pushing the root node (8) into the queue.
Step 3: Process nodes level by level diagonally
- Remove 8 from the queue and keep moving right: we visit 8 → 10 → 14.
- While doing so, we queue the left children: 3 (from 8), and 13 (from 14).
So the first diagonal is: 8, 10, 14
Step 4: Continue with the next set of queued nodes
- Now the queue has 3 and 13.
- Process 3 → 6 → 7, queuing 1 and 4.
Second diagonal: 3, 6, 7, 13
Step 5: Final diagonal
- Queue now has 1 and 4.
- Both have no right children, and no further left children.
Third diagonal: 1, 4
Step 6: Combine all diagonals
Final result after combining diagonals in order: [8, 10, 14, 3, 6, 7, 13, 1, 4]
Edge Cases
Case 1: Empty Tree
If the tree is empty (i.e., the root node is null), then there are no nodes to traverse. Return: []
Case 2: Tree with a Single Node
If the tree has only one node (like 1), then the diagonal traversal is simply [1]
Case 3: Tree with Only Left Children
In a left-skewed tree (each node only has a left child), each node will belong to a separate diagonal.
5
/
4
/
3
Output: [5, 4, 3]
Case 4: Tree with Only Right Children
In a right-skewed tree, all nodes lie on the same diagonal.
1
2
3
Output: [1, 2, 3]
Finally
Diagonal traversal is a unique way to explore a binary tree that isn't covered by typical traversals like inorder, preorder, or level order. By using a queue and traversing right while queueing left children, we maintain control over the diagonals in an intuitive and iterative way. Make sure to always account for edge cases like empty or skewed trees for a complete and robust solution.
Algorithm Steps❯
- If the tree is empty, return an empty result.
- Initialize an empty queue and enqueue the root node.
- While the queue is not empty, dequeue a node and assign it to a temporary variable.
- Traverse along the right pointers of the temporary node:
- Add the node's value to the result.
- If the node has a left child, enqueue the left child.
- Move to the node's right child.
- Repeat until the queue is empty; the collected values represent the diagonal traversal of the tree.
Code
#include <stdio.h>
#include <stdlib.h>
int main() {
printf("Hello from C!\n");
return 0;
}
Sign in with Google
Comments
Loading comments...