InterviewBit Academy is now Scaler!
InterviewBit Academy is now Scaler Academy!

Diagonal Traversal

Problem Description

Consider lines of slope -1 passing between nodes.

Given a Binary Tree A containing N nodes, return all diagonal elements in a binary tree belonging to same line.

NOTE:

  • See Sample Explanation for better understanding.
  • Order does matter in the output.
  • To get the same order as in the output traverse the tree same as we do in pre-order traversal.



Problem Constraints

0 <= N <= 105



Input Format

First and only Argument represents the root of binary tree A.



Output Format

Return a 1D array denoting the diagonal traversal of the tree.



Example Input

Input 1:

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

Input 2:

             11
          /     \
         20      12
        / \       \
       1   15      13
          /  \     /
         2    17  16
          \   /
          22 34



Example Output

Output 1:

 [1, 2, 3, 4, 5, 7, 6, 8, 9]

Output 2:

 [11, 12, 13, 20, 15, 17, 16, 1, 2, 22, 34]



Example Explanation

Explanation 1:

 
 1) Diagonal 1 contains [1, 2, 3]
 2) Diagonal 2 contains [4, 5, 7, 6]
 3) Diagonal 3 contains [8, 9]

NOTE: The order in the output matters like for Example: 6 and 7 belong to same diagonal i.e diagonal 2 but as 7 comes before 6 in pre-order traversal so 7 will be added to answer array first.

So concantenate all the array as return it as a single one. Final output: [1, 2, 3, 4, 5, 7, 6, 8, 9]

Explanation 2:

 
 1) Diagonal 1 contains [11, 12, 13]
 2) Diagonal 2 contains [20, 15, 17, 16]
 3) Diagonal 2 contains [1, 2, 22, 34]

So concantenate all the array as return it as a single one. Final output: [11, 12, 13, 20, 15, 17, 16, 1, 2, 22, 34]



NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Diagonal Traversal   on Interview Code Editor
Sign Up
to access hints and editorial solutions for Diagonal Traversal

Discussion


Loading...
Click here to start solving coding interview questions