Diagonal Traversal of Binary Tree

Diagonal Traversal of a Binary Tree asks you to read a tree along its top-right to bottom-left diagonals. The trick is a single counter, the diagonal index d, that you carry as you walk the tree — and a map that groups nodes by it.

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

The slow way first

You could try to compute, for each node, a pixel-style diagonal coordinate by walking down from the root every time, or sort nodes by some geometric x-position. That is fiddly and easy to get wrong — diagonals are not about screen coordinates, they are about how you got to the node.

The question to ask: what single piece of information decides a node's diagonal? It is simply how many times you turned left on the path from the root. Every right turn is free; every left turn costs one. So we just need to carry that count.

The idea: carry a diagonal index d

Give the root d = 0. As you move down the tree, update d with one rule:

• go to the right child → keep the same d
• go to the left child → use d + 1

For every node you visit, append its value to diag[d] in a map. When the walk finishes, read the map out in increasing order of d and concatenate — that is the diagonal traversal.

The key insight: the diagonal index is inherited and adjusted as you descend. You never recompute it from scratch — each child gets its parent's d, plus 1 if it was a left step.

Walk through it

Step through the animation. We start at the root 8 with d = 0. Following right edges keeps us on diagonal 0, so 8, 10, and 14 all land there. Each left step opens a new diagonal: 8 to 3 reaches d = 1, and from 3 the right child 6 and its right child 7 stay on diagonal 1. Two more left steps (3 to 1, 6 to 4) fill diagonal 2. Finally we read the map by increasing d.

Pseudocode

make an empty map "diag"            # d -> list of node values
queue = [(root, 0)]                 # carry (node, diagonal index)
while the queue is not empty:
    node, d = pop from the queue
    if node is empty: skip it
    append node.value to diag[d]
    push (node.left,  d + 1)        # left -> deeper diagonal
    push (node.right, d)            # right -> same diagonal
read the diagonals in order of d and join them

The Python solution

from collections import defaultdict
 
def diagonal(root):
    diag = defaultdict(list)
    queue = [(root, 0)]
    while queue:
        node, d = queue.pop(0)
        if node is None:
            continue
        diag[d].append(node.val)
        queue.append((node.left, d + 1))
        queue.append((node.right, d))
    result = []
    for d in sorted(diag):
        result.extend(diag[d])
    return result

• diag is a defaultdict(list) mapping a diagonal index → the list of values on that diagonal.
• The queue holds pairs (node, d) so each node travels with its own diagonal index.
• Lines 10–12 are the heart: record the current node under diag[d], then enqueue its children — the left child with d + 1, the right child with the same d.
• The if node is None check lets us blindly enqueue both children and skip the empty ones, which keeps the loop simple.
• At the end we walk the keys in sorted order and flatten — diagonal 0 first, then 1, then 2.

Complexity

We touch each of the n nodes a constant number of times, and the map plus queue hold at most O(n) entries. The only extra cost is sorting the handful of diagonal keys, which is negligible next to the traversal itself.

When this pattern shows up

Practice