Diagonal Traversal of Binary Tree

Medium
1966.

Diagonal Traversal of Binary Tree

Diagonal Traversal of Binary Tree is a medium coding problem on depth-first search, trees and queue, asked in Amazon interviews.

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^5
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var diagonal = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= Node.val <= 10^5

Hints for Diagonal Traversal of Binary Tree

  1. Hint 1

    Following right children never leaves a diagonal, so each diagonal is a set of right-going chains.

  2. Hint 2

    Every chain on diagonal d + 1 starts at the left child of some node on diagonal d.

  3. 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

  1. Put the root in a queue.
  2. 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.
  3. 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 out

Java

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