Diagonal Traversal of Binary Tree — Problem & Solution
Diagonal Traversal of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Diagonal Traversal of Binary Tree is a medium coding problem on depth-first search, trees and queue, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees, Queue
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its diagonal traversal.
Diagonals are lines of slope −1 through the tree: the root is on diagonal 0, a node's right child is on the same diagonal as the node, and its left child is on the next diagonal (one more).
List diagonal 0 first, then diagonal 1, and so on. Within one diagonal, list the nodes in the order a preorder traversal (node, left subtree, right subtree) visits them.
Example 1
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: [8,10,14,3,6,7,13,1,4]
Explanation: Diagonal 0 runs 8 → 10 → 14. Diagonal 1 holds 3, 6, 7 and 13; diagonal 2 holds 1 and 4.
Example 2
Input: root = [1,2,3,4,5,6,7]
Output: [1,3,7,2,5,6,4]
Explanation: Diagonal 0 is 1, 3, 7; diagonal 1 is 2, 5, 6; diagonal 2 is 4.
Example 3
Input: root = [5,4,null,3,null,2]
Output: [5,4,3,2]
Explanation: A left chain puts every node on its own diagonal.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5
Hints for Diagonal Traversal of Binary Tree
Hint 1
Following right children never leaves a diagonal, so each diagonal is a set of right-going chains.
Hint 2
Every chain on diagonal
d + 1starts at the left child of some node on diagonald.Hint 3
Use a queue: pop a node, walk its whole right chain outputting each value, and enqueue every left child met along the way. The queue hands out the chains diagonal by diagonal, in preorder order.
How to solve Diagonal Traversal of Binary Tree
A diagonal is made of right-going chains, and the chains of diagonal d + 1 hang off left children of diagonal d. Processing chains first-in-first-out yields all of diagonal d before any of d + 1, and within a diagonal in preorder order.
Approach
- Put the root in a queue.
- Pop a node and walk from it along right children; output each value on the way and push each node's left child (if any) onto the queue.
- Repeat until the queue is empty.
Why it works
The queue first holds only the root (diagonal 0). Walking diagonal 0's chain enqueues only diagonal-1 nodes; by induction all chains of diagonal d are dequeued before any of diagonal d + 1, since those are enqueued later. Within a diagonal the chains come out in the order their starting points were met, which is the order preorder visits them, and a chain itself is listed top-down — also preorder order.
Complexity
- Time —
O(n) - Space —
O(n) for the queue in the worst case
Pitfalls
- A plain level-order traversal mixes diagonals; the right chain must be walked in full before moving on.
- Grouping by diagonal number with a map works too, but the nodes inside a group must stay in preorder order — append during a preorder walk, not a level-order one.
Reference solution
Python
from collections import deque
from typing import List, Optional
def diagonal(root: Optional[TreeNode]) -> List[int]:
out = []
queue = deque([root]) if root else deque()
while queue:
node = queue.popleft()
while node:
out.append(node.val)
if node.left:
queue.append(node.left)
node = node.right
return outJava
public static int[] diagonal(TreeNode root) {
List<Integer> out = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
while (node != null) {
out.add(node.val);
if (node.left != null) queue.add(node.left);
node = node.right;
}
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> diagonal(TreeNode* root) {
vector<int> out;
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
while (node) {
out.push_back(node->val);
if (node->left) q.push(node->left);
node = node->right;
}
}
return out;
}JavaScript
var diagonal = function(root) {
var out = [];
var queue = root === null ? [] : [root], head = 0;
while (head < queue.length) {
var node = queue[head++];
while (node !== null) {
out.push(node.val);
if (node.left !== null) queue.push(node.left);
node = node.right;
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals