Hello. Thought I’d make it a habit by writing (hopefully) weekly on some coding challenge I work on in my free time. So, welcome to the second article :). Today’s challenge is not actually that much different than the previous one (well, it is different, but not that different). Let’s take a look at Maximum Binary Tree challenge on LeetCode.
The problem is on LeetCode and of difficulty: medium.
The problem is simple: finding the maximum binary tree that can be formed by the given array. I’ll explain more…
You’re given an array, for example, [3,2,1,6,0,5]. The Maximum Binary tree is defined in the problem statement as:
the tree with the root being the maximum value in the array
Well, this means that obviously our maximum element in the given array currently is 6. So, let’s make this our binary tree root.
After picking 6, the problem states that:
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
I believe this screamed recursion at my face!
This basically means that, after picking the max element, 6, we’ll split the array into: [3, 2, 1] (6 was here) and [0, 5]
We will repeat what we did. For (sub)array [3, 2, 1], we’ll:
- pick the max: 3, make it the (sub)tree node
- split the array into , [2, 1]
- pick the max: 2
- split the array into: , 
- pick the max: 1
- no more work.
Our tree now looks like this:
Why are there nulls?
Remember that in recursive algorithms, we need a stopping condition (base case). Otherwise, our recursion will run forever until stack overflows!
Alright, back to the problem. We walked through the recursive algorithm and we sank into the left subtree. If we backtrack and do the same for the remaining [0, 5] part of the array, the tree should look like this:
Nulls removed for readability.
If the current maximum element of a subarray is always in the middle of that subarray, we would have a balanced tree, giving O(log n)since we would have n levels.
In every construction, we would loop on array[start… end] which is a linear, O(n) algorithm. Which gives us, in best condition, O(n log n)
Yet, in average and worst cases, the array isn’t in a specific order, so we might end up with an unbalanced tree which would give us the same time as a linked list: O(n) * O(n) (for calculating max) = O(n²).
Implementation in Java
I’ll leave the explanation in the code comments.
Note: Of course there are more ways to approach this problem, but this is the one I thought easiest to follow.
- Introduction to Algorithms
- Time complexity
- Wikipedia articles on Recursion, Stack, Trees.