Binary TreesProblem 15 of 35

Diagonal Traversal of a Binary tree

Brute Force
Time: O(n log n)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given a binary tree, print all diagonal elements. The diagonal of a tree is defined as nodes that can be reached by starting from any node and repeatedly going to the right child (or starting from root and going left once, then repeatedly going right).

Example:

1 / \ 2 3 / \ \ 4 5 6 / 7
  • Diagonal 0: 1, 3, 6
  • Diagonal 1: 2, 5
  • Diagonal 2: 4, 7

Output: [1, 3, 6, 2, 5, 4, 7] or [[1, 3, 6], [2, 5], [4, 7]]

Approach 1: Using Map with Diagonal Number

Intuition

Assign a diagonal number to each node. Root is on diagonal 0. Going right keeps the same diagonal, going left increases diagonal by 1. Group nodes by their diagonal number.

Algorithm

  1. Use DFS/BFS to traverse the tree
  2. Track diagonal number for each node
  3. Store nodes in a map keyed by diagonal number
  4. Extract nodes in order of diagonals
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // DFS approach
    private void diagonalDFS(TreeNode root, int diagonal, 
                             TreeMap<Integer, List<Integer>> diagonalMap) {
        if (root == null) return;
        
        diagonalMap.computeIfAbsent(diagonal, k -> new ArrayList<>()).add(root.val);
        
        // Right child - same diagonal
        diagonalDFS(root.right, diagonal, diagonalMap);
        
        // Left child - next diagonal
        diagonalDFS(root.left, diagonal + 1, diagonalMap);
    }
    
    public List<List<Integer>> diagonalTraversal(TreeNode root) {
        TreeMap<Integer, List<Integer>> diagonalMap = new TreeMap<>();
        diagonalDFS(root, 0, diagonalMap);
        return new ArrayList<>(diagonalMap.values());
    }
    
    public List<Integer> diagonalTraversalFlat(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeMap<Integer, List<Integer>> diagonalMap = new TreeMap<>();
        diagonalDFS(root, 0, diagonalMap);
        
        for (List<Integer> diagonal : diagonalMap.values()) {
            result.addAll(diagonal);
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) - Due to map operations and sorting
  • Space Complexity: O(n) - Map stores all nodes

Approach 2: Optimal (Using Queue - BFS Style)

Intuition

Process nodes diagonal by diagonal using a queue. For each node, go right as far as possible (same diagonal), then add left children to queue (next diagonal).

Algorithm

  1. Start with root in queue
  2. For each node, traverse right and collect all nodes
  3. Add left children of visited nodes to queue
  4. These left children form the next diagonal
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<List<Integer>> diagonalTraversalBFS(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currentDiagonal = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                
                // Traverse right and collect nodes
                while (node != null) {
                    currentDiagonal.add(node.val);
                    
                    // Add left child to queue (for next diagonal)
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    
                    // Move right (same diagonal)
                    node = node.right;
                }
            }
            
            result.add(currentDiagonal);
        }
        
        return result;
    }
    
    public List<Integer> diagonalTraversalBFSFlat(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            
            while (node != null) {
                result.add(node.val);
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                
                node = node.right;
            }
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each node is visited exactly once
  • Space Complexity: O(n) - Queue can hold up to n/2 nodes (width of tree)

Key Takeaways

  1. Diagonal definition: Going right stays on same diagonal, going left increases diagonal
  2. Two approaches: Map with diagonal index vs BFS-style queue processing
  3. BFS approach is more efficient - O(n) vs O(n log n)
  4. The BFS approach naturally groups nodes by diagonal
  5. Pattern: Right movement = same group, left movement = next group
  6. This is a variation of level order traversal with different grouping logic
Previous
Check if a tree is balanced or not
Next
Boundary traversal of a Binary tree