Diagonal Traversal of a Binary Tree - Iterative Approach

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given a binary tree, perform a diagonal traversal of the tree using an iterative approach. In diagonal traversal, all nodes having the same slope distance from the root are grouped together. The traversal proceeds diagonally from top-right to bottom-left.

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

Visualization Player

Solution❯

Case 1: Empty Tree

If the binary tree is empty (i.e., the root node is null), there are no nodes to process. In this case, the output should simply be an empty list [].

Case 2: Tree with a Single Node

If the tree has only one node (the root), then the diagonal traversal consists of just that node. For example, a tree with only the node 1 will return [1].

Case 3: General Tree with Multiple Nodes

For a more complex binary tree, diagonal traversal collects all nodes that lie along the same diagonal, starting from the root. A diagonal is formed by starting at a node and repeatedly moving to the right child. Whenever a node has a left child, that child belongs to the next diagonal and is queued for later processing.

For example, in the tree:

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

The diagonal groups would be:

  • Diagonal 1: 8, 10, 14
  • Diagonal 2: 3, 6, 7, 13
  • Diagonal 3: 1, 4

We process each diagonal by traversing right while queuing the left children, resulting in the output: [8, 10, 14, 3, 6, 7, 13, 1, 4].

This iterative approach makes use of a queue to manage left children and continues moving to the right along each diagonal line. This ensures we collect nodes in the correct diagonal grouping order.

Algorithm Steps❯

  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.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diagonalTraversal(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        while node:
            result.append(node.val)
            if node.left:
                queue.append(node.left)
            node = node.right
    return result

if __name__ == '__main__':
    # Example tree:
    #          8
    #        /   \
    #       3     10
    #      / \      \
    #     1   6      14
    #        / \     /
    #       4   7   13
    root = TreeNode(8,
            TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
            TreeNode(10, None, TreeNode(14, TreeNode(13))))
    print(diagonalTraversal(root))