Diagonal Traversal of a binary tree.
You have been given a binary tree of integers. You are supposed to find the diagonal traversal(refer to Example) of the given binary tree.

Example:

Consider lines at an angle of 135 degrees(with respect to standard X- axis) in between nodes. Then, all nodes between two consecutive lines belong to the same diagonal

The diagonal traversal for the above tree is: 0 2 6 1 5 3 4 7

Input Format:

The first line contains an integer 'T' which denotes the number of test cases. The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. So -1 would not be a part of the tree nodes.

Example:

The input for the tree depicted in the below image will be:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 : The root node of the tree is 1 Level 2 : Left child of 1 = 2 Right child of 1 = 3 Level 3 : Left child of 2 = 4 Right child of 2 = null (-1) Left child of 3 = 5 Right child of 3 = 6 Level 4 : Left child of 4 = null (-1) Right child of 4 = 7 Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 6 = null (-1) Right child of 6 = null (-1) Level 5 : Left child of 7 = null (-1) Right child of 7 = null (-1) 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Note :

1. The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. 2.The input ends when all nodes at the last level are null(-1).

Output Format :

For each test case, return the diagonal traversal of the binary tree separated by a single space.

Note :

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Diagonal Traversal of a binary tree.

You have been given a binary tree of integers. You are supposed to find the diagonal traversal(refer to Example) of the given binary tree.

Example:

Consider lines at an angle of 135 degrees(with respect to standard X- axis)  in between nodes. Then, all nodes between two consecutive lines belong to the same diagonal

alt text

The diagonal traversal for the above tree is: 

0 2 6 1 5 3 4 7

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. So -1 would not be a part of the tree nodes.

Example:

The input for the tree depicted in the below image will be:

alt text

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Note :

1. The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

2.The input ends when all nodes at the last level are null(-1).

Output Format :

For each test case, return the diagonal traversal of the binary tree separated by a single space.

Note :

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
0 <= N <= 3000
0 <= data <= 10^5 and data!=-1

Where ‘N’ is the total number of nodes in the binary tree, and 'data' is the value of the binary tree node

Time limit : 1 sec

Accepted Answer

Map based approach

The idea is to use the Map to store all the nodes of a particular diagonal number. We will use preorder traversal to update the Map. The key of the Map will be the diagonal number and the value of the Map will be an array/list that will store all nodes belonging to that diagonal.

The steps are as follows:

Assign the diagonal number of the root as 0.
Do a preorder traversal of the binary tree and for each node keep track of the diagonal number.
- Insert the value of the current node in the Map with the key as the diagonal number of the current node.
- Now increase the diagonal number by 1 for the left child of the node and recursively traverse the left subtree.
- Recursively traverse the right subtree and keep the diagonal number the same as the current node.
Initialize an empty array to store the diagonal traversal, let’s say 'traversal'
Iterate through the Map and add all the values of the Map to 'traversal'.
Finally, Return 'traversal'.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the total number of nodes in the binary tree.

Since we are storing the value of all nodes in the Map which will take O(N) space. We are also storing all the values of the Map in an array/list, which will also take O(N) space. Thus, the total space complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

O(N * log N), Where ‘N’ is the total number of nodes in the binary tree.

Since we are doing diagonal traversal which will visit each node of the given binary tree exactly once. Also, we are inserting ‘N’ values into the Map, and inserting each value takes (log N) time on average. Thus, the total time complexity will be O(N * log N).

Python (3.5)

"""
    Time Complexity - O(N * log N)
    Space Complexity - O(N)

    Where 'N' is the number of nodes in the Binary Tree.
"""

# Function for doing preorder traversal.
def preorderTraversal(root, diagonalNumber, diagonal):
    # Return if the current node is None.
    if (root == None):
        return
    
    # Push the current node in the Dictionary with key as the diagonal number.
    if diagonalNumber not in diagonal.keys():
        diagonal[diagonalNumber] = []

    diagonal[diagonalNumber].append(root.data)

    # Recursively traverse the left subtree
    preorderTraversal(root.left, diagonalNumber + 1, diagonal)

    # Recursively traverse the right subtree.
    preorderTraversal(root.right, diagonalNumber, diagonal)

def diagonalTraversal(root):
    # Dictionary for storing nodes corresponding to each diagonal number.
    diagonal = {}

    # Preorder Traversal to update the Dictionary.
    preorderTraversal(root, 0, diagonal)

    # List for storing the final diagonal traversal.
    traversal = []

    # Iterate through the Dictionary.
    for i in diagonal.values():
        # Push the elements into the list.
        for j in i:
            traversal.append(j)
        
    # Return the final traversal.
    return traversal

Java (SE 1.8)

/*
    Time Complexity - O(N * log N)
    Space Complexity - O(N)

    Where 'N' is the number of nodes in the Binary Tree.
*/

import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;

public class Solution {
    // Function for doing preorder traversal.
    private static void preorderTraversal(TreeNode root, int diagonalNumber, Map> diagonal) {
        // Return if the current node is NULL.
        if (root == null) {
            return;
        }

        // Push the current node in the Map with key as the diagonal number.
        ArrayList mapItem = diagonal.get(diagonalNumber);

        if (mapItem == null) {
            mapItem = new ArrayList();
        }

        mapItem.add(root.data);
        diagonal.put(diagonalNumber, mapItem);

        // Recursively traverse the left subtree.
        preorderTraversal(root.left, diagonalNumber + 1, diagonal);

        // Recursively traverse the right subtree.
        preorderTraversal(root.right, diagonalNumber, diagonal);
    }

    public static ArrayList diagonalTraversal(TreeNode root) {
        // Map for storing nodes corresponding to each diagonal number.
        Map> diagonal = new TreeMap>();

        // Preorder Traversal to update the Map.
        preorderTraversal(root, 0, diagonal);

        // ArrayList for storing the final diagonal traversal.
        ArrayList traversal = new ArrayList();

        // Iterate through the Map.
        for (Map.Entry> item : diagonal.entrySet()) {
            // Push the elements into the arraylist.
            for (int i = 0; i < item.getValue().size(); i++) {
                traversal.add(item.getValue().get(i));
            }
        }
        // Return the final traversal.
        return traversal;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity - O(N * log N)
    Space Complexity - O(N)

    Where 'N' is the number of nodes in the Binary Tree.
*/

#include 

// Function for doing preorder traversal.
void preorderTraversal(TreeNode *root, int diagonalNumber, map> &diagonal) {
    // Return if the current node is NULL.
    if (root == NULL) {
        return;
    }

    // Push the current node in the Map with key as the diagonal number.
    diagonal[diagonalNumber].push_back(root->data);

    // Recursively traverse the left subtree.
    preorderTraversal(root->left, diagonalNumber + 1, diagonal);

    // Recursively traverse the right subtree.
    preorderTraversal(root->right, diagonalNumber, diagonal);
}

vector diagonalTraversal(TreeNode *root) {
    // Map for storing nodes corresponding to each diagonal number.
    map> diagonal;

    // Preorder Traversal to update the Map.
    preorderTraversal(root, 0, diagonal);

    // Array for storing the final diagonal traversal.
    vector traversal;

    // Iterate through the Map.
    for (auto i : diagonal) {
        // Push the elements into the array.
        for (int j : i.second) {
            traversal.push_back(j);
        }
    }
    // Return the final traversal.
    return traversal;
}

You have been given a binary tree of integers. You are supposed to find the diagonal traversal(refer to Example) of the given binary tree.

Example:

Input Format:

Example:

Explanation :

Note :

Output Format :

Note :

Constraints :

Top Amazon Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Amazon Software Developer Intern