Diagonal Traversal of a Binary Tree

Algorithm Steps

If the tree is empty, return an empty result.
Initialize an empty queue and enqueue the root node.
While the queue is not empty, dequeue a node and assign it to a temporary variable.
Traverse along the right pointers of the temporary node:

Add the node's value to the result.
If the node has a left child, enqueue the left child.
Move to the node's right child.

Repeat until the queue is empty; the collected values represent the diagonal traversal of the tree.

Diagonal Traversal of a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diagonalTraversal(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        while node:
            result.append(node.val)
            if node.left:
                queue.append(node.left)
            node = node.right
    return result

if __name__ == '__main__':
    # Example tree:
    #          8
    #        /   \
    #       3     10
    #      / \      \
    #     1   6      14
    #        / \     /
    #       4   7   13
    root = TreeNode(8,
            TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
            TreeNode(10, None, TreeNode(14, TreeNode(13))))
    print(diagonalTraversal(root))