Maximum Binary Tree

Moderate
0/80
Average time to solve is 10m
3 upvotes
Asked in companies
AdobeMorgan Stanley

Problem statement

You have been given an array/list ‘TREE’ having ‘N’ unique integers. You need to make a maximum binary tree recursively from ‘TREE’ using the following conditions:

1. Create a root of the maximum binary tree whose value is the maximum value present in the ‘TREE’.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

For example:

For ‘TREE’ = [6, 1, 8, 2, 5],see the maximum binary tree in the below picture for reference:

img

As we can see the root of the maximum binary tree as shown in the picture is ‘8’ which is the maximum value in the ‘TREE’. The left subtree contains all the values which are present in the left of 8  in ‘TREE’ and the right subtree contains all the values which are present in the right of ‘8’ in ‘TREE’. Similarly, the maximum value in the left subarray of 8 is 6 so 6 becomes the root of the left subtree, 5 is the maximum value in the right subarray of the 8 so 5 becomes the root of the right subarray, and so on.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains an integer ‘N’ representing the number of elements in the ‘TREE’.

The second line of each test case contains ‘N’ space separated integers denoting the values of ‘TREE’.
Output Format : 
For each test case, print the level order traversal of the maximum binary tree formed using the array/list ‘TREE’.

The output for each test case is printed in a separate line.
Note: 
You are not required to print the expected output; it has already been taken care of, Just implement the function.
Constraints : 
1 <= T <= 100
1 <= N <= 10 ^ 4
1 <= TREE[i] <= 10 ^ 4 

Time limit: 1 second
Sample Input 1 :
2
2
1 5
3
8 10 2
Sample Output 1:
5 1  
10 8 2

Explanation for Sample Output 1:

For the first test case :
See the picture below for the output reference:

img

For the second test case :
See the picture below for the output reference:

img

Sample Input 2 :
2
1
8
5
12 3 15 1 11
Sample Output 2 :
8
15 12 11 3 1
Hint

Try to use recursion in this problem.

Approaches (1)
Recursion

This approach aims to find the maximum element in ‘TREE’ and make it the root of the current binary tree. For the left and right subtree, we use the same approach using the left and right subarray, respectively.

 

We use the function ‘CONSTRUCT_MAX_TREE’ with three arguments ‘TREE’, ‘l’ and ‘r’, which will return the root of the maximum binary tree consisting of numbers within the indices ‘l’ and ‘r’ of the ‘TREE’.

 

Here is the complete algorithm:

  • We call the function ‘CONSTRUCT_MAX_TREE’  and pass ‘TREE’, 0 and ‘N’.
  • Find the index of the maximum element in the range ‘l’ to ‘r’ and store it in ‘MAX_ELEMENT_INDEX’.
  • Make the element at ‘MAX_ELEMENT_INDEX’ index as the local root node.
  • Determine the left child of the root using the function ‘CONSTRUCT_MAX_TREE’ and pass ‘TREE’, ‘l’, ‘MAX_ELEMENT_INDEX’. Doing this recursively finds the largest element in the subarray left to the current largest element.
  • Determine the right child of the root using the function ‘CONSTRUCT_MAX_TREE’ and pass ‘TREE’, ‘MAX_ELEMENT_INDEX + 1’, ‘r’. Doing this recursively finds the largest element in the subarray right to the current largest element.
  • Return the root node to the calling function.
Time Complexity

O(N ^ 2), where ‘N’ represents the number of elements in the array/list ‘TREE’.

 

The function ‘CONSTRUCT_MAX_TREE’ is called ‘N’ times. At each level of the recursive tree, we traverse over all the ‘N’ elements to find the maximum element. So in the worst case, the depth of the recursive tree can grow upto ‘N’, which happens in the case of a sorted ‘TREE’. So the overall time complexity will be O(N ^ 2).

Space Complexity

O(N), where N represents the number of elements in the array/list ‘TREE’.

 

Because the size of the recursion tree can grow upto ‘N’ in the worst case when ‘TREE’ will be sorted. Hence the overall time complexity will be O(N).

Code Solution
(100% EXP penalty)
Maximum Binary Tree
Full screen
Console