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

Deserialize Binary Tree

Problem Description

Given an integer array A denoting the Level Order Traversal of the Binary Tree.

You have to Deserialize the given Traversal in the Binary Tree and return the root of the Binary Tree.

NOTE:

  • In the array, the NULL/None child is denoted by -1.
  • For more clarification check the Example Input.


  • Problem Constraints

    1 <= number of nodes <= 105

    -1 <= A[i] <= 105



    Input Format

    Only argument is an integer array A denoting the Level Order Traversal of the Binary Tree.



    Output Format

    Return the root node of the Binary Tree.



    Example Input

    Input 1:

     A = [1, 2, 3, 4, 5, -1, -1, -1, -1, -1, -1]

    Input 2:

     A = [1, 2, 3, 4, 5, -1, 6, -1, -1, -1, -1, -1, -1]



    Example Output

    Output 1:

               1
             /   \
            2     3
           / \
          4   5
    

    Output 2:

                1
              /   \
             2     3
            / \ .   \
           4   5 .   6
    



    Example Explanation

    Explanation 1:

     Each element of the array denotes the value of the node. If the val is -1 then it is the NULL/None child.
     Since 3, 4 and 5 each has both NULL child we had represented that using -1.

    Explanation 2:

     Each element of the array denotes the value of the node. If the val is -1 then it is the NULL/None child.
     Since 3 has left child as NULL while 4 and 5 each has both NULL child.



    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 Deserialize Binary Tree on Interview Code Editor
    Sign Up
    to access hints and editorial solutions for Deserialize Binary Tree

    Discussion


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