Log inSign up
mediumgeeksforgeeksNot Started

Diagonal Traversal of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on geeksforgeeks
Lesson

Problem Statement

Given a binary tree, print all diagonal elements in a binary tree from top to bottom and left to right.

All nodes reachable by repeatedly going right from a node belong to the SAME diagonal slope (slope = 0). Moving left moves to the next diagonal (slope = d + 1).

Example 1 · Example 1: Standard Tree:

Input: root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13] Tree: 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13
Output: [8, 10, 14, 3, 6, 7, 13, 1, 4]
Explanation: Diagonal 0: [8, 10, 14]. Diagonal 1: [3, 6, 7, 13]. Diagonal 2: [1, 4].

Example 2 · Example 2: Small Tree:

Input: root = [1, 2, 3] Tree: 1 / \ 2 3
Output: [1, 3, 2]
Explanation: Diagonal 0: [1, 3]. Diagonal 1: [2].

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Data of a node <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model tree diagonal slopes mathematically (left = d + 1, right = d).
  • Implement the elegant iterative right spine traversal with a left-child queue.
  • Eliminate hash map grouping overhead using direct queue flow.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Diagonal order traversal.
  • Slope-based grouping in trees.
  • Traversing right spines while buffering left children.

Algorithmic Decision Tree:

  • While node != null: collect node.val; if left child exists, push to queue; move node = node.right.
  • Pop next left child from queue and repeat.

Connected Patterns:

Boundary Traversal of Binary TreeVertical Order TraversalBinary Tree Right Side View

1. Recursive DFS with Diagonal Map

Intuition

Traverse tree with DFS. Maintain integer d. For left child, d + 1. For right child, d. Group nodes into map[d] and concatenate.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Helper dfs(node, d, map).
  2. Step 2: If node == null return.
  3. Step 3: map[d].push_back(node.val).
  4. Step 4: dfs(node.left, d + 1, map).
  5. Step 5: dfs(node.right, d, map). Concatenate map entries.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int d, map<int, vector<int>>& m) {
10 if (!node) return;
11 m[d].push_back(node->val);
12 dfs(node->left, d + 1, m);
13 dfs(node->right, d, m);
14 }
15 vector<int> diagonal(TreeNode* root) {
16 map<int, vector<int>> m;
17 dfs(root, 0, m);
18 vector<int> res;
19 for (auto& p : m) {
20 for (int v : p.second) res.push_back(v);
21 }
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n log n) — Traversing n nodes plus ordered map insertion/lookup.
  • Space complexity: O(n) — Map stores all n nodes plus recursion stack.

2. Unordered Hash Map with Max Diagonal Tracking

Intuition

Track maxD during DFS and iterate from 0 to maxD to collect nodes in O(n) time.

When to apply: DFS without sorting overhead.

Algorithm

  1. Step 1: Traverse with DFS, populating unordered map.
  2. Step 2: Update maxD = max(maxD, d).
  3. Step 3: Loop d from 0 to maxD and append map[d] to result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int maxD = 0;
9 void dfs(TreeNode* node, int d, unordered_map<int, vector<int>>& m) {
10 if (!node) return;
11 maxD = max(maxD, d);
12 m[d].push_back(node->val);
13 dfs(node->left, d + 1, m);
14 dfs(node->right, d, m);
15 }
16public:
17 vector<int> diagonal(TreeNode* root) {
18 if (!root) return {};
19 unordered_map<int, vector<int>> m;
20 dfs(root, 0, m);
21 vector<int> res;
22 for (int d = 0; d <= maxD; ++d) {
23 for (int v : m[d]) res.push_back(v);
24 }
25 return res;
26 }
27};
28
29int main() {
30 // Sample driver execution
31 cout << "Execution completed successfully." << endl;
32 return 0;
33}
34

Time & Space Complexity

  • Time complexity: O(n) — All nodes inserted and retrieved in O(1) average time.
  • Space complexity: O(n) — Hash map holds all n nodes.

3. Iterative Right Spine Traversal with Left Child Queue

Intuition

Initialize queue with root. For each node popped, traverse down its entire right spine with a while loop (curr != null): add curr.val directly to result, push curr.left into queue, and advance curr = curr.right. This outputs elements directly in diagonal order with zero extra maps.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Initialize queue q; push root.
  3. Step 3: While q is not empty: pop node curr.
  4. Step 4: While curr is not null: add curr.val to result; if curr.left != null q.push(curr.left); curr = curr.right.
  5. Step 5: Return result.

Diagonal Walk Trace for root = [1, 2, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at root 1 (Diagonal 0)
Visual state
Values and pointers at this exact step
tree
Root
1 (Diag 0)
L
2
R
3

Node order shown; add connections to display explicit tree edges.

diag 0: 1
Check / comparison
Add 1 to diagonal 0. Left child 2 queued.
Decision / next transition
Result: [1]. Move to 3.
Why this step matters

Step 1: Start at root 1 (Diagonal 0). Enqueue left child 2 for next diagonal. Move to right child 3.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> diagonal(TreeNode* root) {
10 if (!root) return {};
11 vector<int> res;
12 queue<TreeNode*> q;
13 q.push(root);
14 while (!q.empty()) {
15 TreeNode* cur = q.front(); q.pop();
16 while (cur) {
17 res.push_back(cur->val);
18 if (cur->left) q.push(cur->left);
19 cur = cur->right;
20 }
21 }
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once and pushed to queue at most once.
  • Space complexity: O(n) — Queue holds at most number of left children <= n.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with Ordered MapO(n log n)O(n)Recursively tag nodes with diagonal index d; tree map groups them.Ordered map.
2.DFS with Max Diagonal IntegerO(n)O(n)Hash map grouping with maxD bounds tracking.Map allocations.
3.Iterative Right Spine Walk with QueueOptimalO(n)O(n)While loop walks right spine directly; queue stores left children.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: returns [root.val].
  • Completely right-skewed: all nodes belong to diagonal 0; processed in one straight pass.
  • Completely left-skewed: every node starts a new diagonal.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Demonstrate the queue-based iterative approach: it processes nodes in the exact requested output order without needing a map.
  2. Highlight the invariant: moving right never changes the diagonal slope.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does traversing curr = curr.right in a while loop process all nodes in the same diagonal without changing the diagonal index?

Back to DSA Sheet