Diagonal Traversal of Binary Tree

In this article, we will tackle the problem of performing diagonal traversal of a binary tree. Diagonal traversal involves visiting nodes of the binary tree in a diagonal pattern, starting from the top-left and moving towards the bottom-right. We will explore how to implement this traversal in Java and print the nodes in the diagonal order.

Problem Statement

Given a binary tree, we want to perform a diagonal traversal of the tree. Diagonal traversal means visiting nodes in a diagonal pattern from the top-left to the bottom-right, where nodes with the same diagonal distance are visited together. For each diagonal, we will print the nodes from top to bottom.

Example

Let's consider a binary tree as an example:

    10
    / \ 
   /   \
  2     4
 /    /  \
3    6    \
    / \    \
   1   7    5
      /    /
     9    3

The diagonal traversal of this tree results in the following output:

10 4 5
2 6 7 3
3 1 9

Nodes with the same diagonal distance are visited together, and we move from the top-left to the bottom-right diagonally.

Idea to Solve the Problem

To perform diagonal traversal of the binary tree, we can use a recursive approach. We will keep track of the diagonal distance of each node from the root and store nodes with the same diagonal distance in a data structure, such as an ArrayList, associated with that distance. We will start from the root with a diagonal distance of 0, and as we move to the left child, we increment the diagonal distance by 1, and when we move to the right child, we keep the same diagonal distance. We will use a HashMap to store the nodes at each diagonal distance.

Pseudocode

Here is the pseudocode for solving the problem:

function getDiagonalView(node, distance, record):
        if node is not null:
            if distance not in record:
                record[distance] = new ArrayList()
            record[distance].add(node.data)
            getDiagonalView(node.left, distance + 1, record)
            getDiagonalView(node.right, distance, record)
    
    function diagonalView():
        record = empty HashMap
        getDiagonalView(root, 0, record)
        distance = 0
        while distance in record:
            for node in record[distance]:
                print node
            increment distance by 1

Algorithm Explanation

1. Initialize an empty HashMap called record to store nodes at each diagonal distance.
2. Call the getDiagonalView function starting from the root node with an initial distance of 0.
3. In the getDiagonalView function:
   • If the current node is not null, check if the current distance is already in record. If not, create a new ArrayList for that distance.
   • Add the node's data to the ArrayList associated with the current distance.
   • Recursively call the function for the left child with an incremented distance (moving diagonally down to the left).
   • Recursively call the function for the right child with the same distance (moving diagonally down to the right).
4. After the traversal is complete, iterate through the record map, starting from distance 0, and print the nodes in each diagonal distance.
5. Increment the distance by 1 in each iteration until all diagonal distances are printed.

Code Solution

1) Diagonal traversal of binary tree in java 2) Diagonal traversal of binary tree in c++ 3) Diagonal traversal of binary tree in c# 4) Diagonal traversal of binary tree in vb.net 5) Diagonal traversal of binary tree in php 6) Diagonal traversal of binary tree in node js 7) Diagonal traversal of binary tree in typescript 8) Diagonal traversal of binary tree in python 9) Diagonal traversal of binary tree in ruby 10) Diagonal traversal of binary tree in scala 11) Diagonal traversal of binary tree in swift 12) Diagonal traversal of binary tree in kotlin 13) Diagonal traversal of binary tree in golang

Time Complexity of the Code

The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the depth-first traversal, and the HashMap operations take constant time.