Diagonal Traversal of a Binary Tree - Iterative - Visualization

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.

1. If the tree is empty, return an empty result.
2. Initialize an empty queue and enqueue the root node.
3. While the queue is not empty, dequeue a node and assign it to a temporary variable.
4. Traverse along the right pointers of the temporary node:
1. Add the node's value to the result.
2. If the node has a left child, enqueue the left child.
3. Move to the node's right child.
5. Repeat until the queue is empty; the collected values represent the diagonal traversal of the tree.