Approach 1: Recursive Solution
The current solution is very simple. We make use of a function
construct(nums, l, r), which returns the maximum binary tree consisting of numbers within the indices and in the given array(excluding the element).
The algorithm consists of the following steps:
Start with the function call
construct(nums, 0, n). Here, refers to the number of elements in the given array.
Find the index, , of the largest element in the current range of indices . Make this largest element, as the local root node.
Determine the left child using
construct(nums, l, max_i). Doing this recursively finds the largest element in the subarray left to the current largest element.
Similarly, determine the right child using
construct(nums, max_i + 1, r).
Return the root node to the calling function.
Time complexity : . The function
constructis called times. At each level of the recursive tree, we traverse over all the elements to find the maximum element. In the average case, there will be a levels leading to a complexity of . In the worst case, the depth of the recursive tree can grow upto , which happens in the case of a sorted array, giving a complexity of .
Space complexity : . The size of the can grow upto in the worst case. In the average case, the size will be for elements in , giving an average case complexity of
Analysis written by: @vinod23