# Maximum Binary Tree

• Can you flesh our the Time complexity using recurrence relations? It is stated that the average case is nlogn, but don't you mean the best (aka balanced tree) case?

• Are you good with the relation being approx: T(n) = O(n) + 2T(n/2)? You can then look at the above link and see that it is nlogn.

I guess it is more like T(n) = O(n) + T(m) + T(n-m)

• O(n) complexity and O(n) space JAVA Solution

/**

• Definition for a binary tree node.

• public class TreeNode {

• ``````int val;
``````
• ``````TreeNode left;
``````
• ``````TreeNode right;
``````
• ``````TreeNode(int x) { val = x; }
``````
• }
*/
class Solution {
TreeNode root = null;
HashMap<TreeNode,TreeNode> parentMap = new HashMap<>();
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length==0) return null;

`````` TreeNode current = new TreeNode(nums[0]);
root = current;
for(int idx=1; idx<nums.length; idx++) {
TreeNode newNode = new TreeNode(nums[idx]);
if(newNode.val<current.val) {
//next element value less than current. next element goes to the right of current
current.right=newNode;
parentMap.put(newNode, current);
current=newNode;
} else {
//find its correct position
insertNode(current, newNode);
current=newNode;
}
}
return root;
``````

}
public void insertNode(TreeNode current, TreeNode newNode) {
//iterate till I get parent greater than new element or new element is new root.
while(parentMap.get(current)!=null && parentMap.get(current).val<newNode.val) {
current = parentMap.get(current);
}
if(parentMap.get(current)==null) {
//if new element is root
root = newNode;
newNode.left = current;
parentMap.put(current, newNode);
} else {
//Noew parent is greater than new element. It will always come from right subtree. Thus make the new element right child of parent and current right subtree the left child(the whole left sub tree came before new element) of new element.
TreeNode parent = parentMap.get(current);
TreeNode temp = parent.right;
parent.right=newNode;
newNode.left = temp;
parentMap.put(newNode, parent);
parentMap.put(current, newNode);
}
}
}

• O(n) complexity and O(n) space JAVA Solution

class Solution {
TreeNode root = null;
HashMap<TreeNode,TreeNode> parentMap = new HashMap<>();
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length==0) return null;

``````    TreeNode current = new TreeNode(nums[0]);
root = current;
for(int idx=1; idx<nums.length; idx++) {
TreeNode newNode = new TreeNode(nums[idx]);
if(newNode.val<current.val) {
//next element value less than current. next element goes to the right of current
current.right=newNode;
parentMap.put(newNode, current);
current=newNode;
} else {
//find its correct position
insertNode(current, newNode);
current=newNode;
}
}
return root;
}
public void insertNode(TreeNode current, TreeNode newNode) {
//iterate till I get parent greater than new element or new element is new root.
while(parentMap.get(current)!=null && parentMap.get(current).val<newNode.val) {
current = parentMap.get(current);
}
if(parentMap.get(current)==null) {
//if new element is root
root = newNode;
newNode.left = current;
parentMap.put(current, newNode);
} else {
//Noew parent is greater than new element. It will always come from right subtree. Thus make the new element right child of     parent and current right subtree the left child(the whole left sub tree came before new element) of new element.
TreeNode parent = parentMap.get(current);
TreeNode temp = parent.right;
parent.right=newNode;
newNode.left = temp;
parentMap.put(newNode, parent);
parentMap.put(current, newNode);
}
}
``````

}

• iterative way to o(n) time complexity and o(n) space complexity.
Use deque because need to use the front element of stack at the last step.

This solution is inspired by @votrubac
https://discuss.leetcode.com/topic/98454/c-9-lines-o-n-log-n-map

1. traverse the array once and create the node one by one. and use stack to store a decreasing sequence.
2, each step when we create a new curNode. compare to the peek of stack,
2.a . keep popping the stack while the peek < curNode, and set the last popping node to be curNode.left. Because the last one is the largest number among curNode's left children. => curNode.left = last pop node
2.b . after popping up all (node.val < curNode), the peek is curNode's root => peek.right = curNode
3 return the first element of stack.

Because of the last step, I use Deque to do all operations.

class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}

``````    Deque<TreeNode> dq = new LinkedList();

for (int i = 0; i < nums.length; i++) {
TreeNode curNode = new TreeNode(nums[i]);

while (!dq.isEmpty() && dq.peek().val < nums[i]) {
curNode.left = dq.peek();
dq.pop();
}

if (!dq.isEmpty()) {
dq.peek().right = curNode;

}
dq.push(curNode);
}

return dq.peekLast();
}
``````

}

• /**

• Definition for a binary tree node.

• public class TreeNode {

• ``````int val;
``````
• ``````TreeNode left;
``````
• ``````TreeNode right;
``````
• ``````TreeNode(int x) { val = x; }
``````
• }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {

`````` int max=0;
int maxIndex=0;

for(int i=0;i<nums.length;i++){
if(nums[i]>max){
max=nums[i];
maxIndex=i;
}
}
TreeNode root=new TreeNode(max);
``````

if(maxIndex!=0 && nums.length!=0){
int leftArray[] = Arrays.copyOfRange(nums, 0, maxIndex);
root.left=constructMaximumBinaryTree(leftArray);
}
if(maxIndex!=nums.length-1 && nums.length!=0) {
int rightArray[] = Arrays.copyOfRange(nums, maxIndex+1, nums.length);
root.right=constructMaximumBinaryTree(rightArray);
}
return root;
}
}

• I think a simple O(nlogn) solution should be included as one of the accepted solutions: see the code: https://repl.it/@toravir/QuickDizzyPaintedladybutterfly

• Python code:

``````def constructMaximumBinaryTree(self, nums):
if nums is None:
return None

new_val=max(nums)
split_index=nums.index(new_val)
node=TreeNode(new_val)
if len(nums[:split_index]):
node.left=self.constructMaximumBinaryTree(nums[:split_index])
if len(nums[split_index+1:]):
node.right=self.constructMaximumBinaryTree(nums[split_index+1:])

return node``````

• You could have used a HashMap to store array position and MaxHeap.

``````    public TreeNode constructMaximumBinaryTree(int[] nums) {
HashMap<Integer,Integer> hash = populateHash(nums);
PriorityQueue<Integer> maxHeap = populateMaxHeap(nums);
TreeNode root = new TreeNode(maxHeap.poll());
while(!maxHeap.isEmpty()){
TreeNode node = new TreeNode(maxHeap.poll());
}

return root;
}

private HashMap<Integer, Integer> populateHash(int[] nums){
HashMap<Integer,Integer> hash = new HashMap<>();

for(int idx=0; idx<nums.length; idx++){
hash.put(nums[idx], idx);
}
return hash;
}

private PriorityQueue<Integer>  populateMaxHeap(int[] nums){
PriorityQueue<Integer> que = new PriorityQueue(1,new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){
return -1 * a.compareTo(b);
}

});

for(int idx=0; idx<nums.length; idx++){
}
return que;
}

private void addNode(TreeNode root, TreeNode node, HashMap<Integer,Integer> hash){
TreeNode parent = root;
int nodePos = hash.get(node.val);

while(parent!= null){
int parentPos = hash.get(parent.val);
if(nodePos<parentPos){
if(parent.left==null){
parent.left = node;
break;
}
parent = parent.left;
}else{
if(parent.right==null){
parent.right = node;
break;
}
parent = parent.right;
}
}
}

}
``````

• The following solution uses a Segment Tree to find the max value within any range in the array.

``````
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

private int segment[] = {};

public TreeNode constructMaximumBinaryTree(int[] nums) {
this.segment = new int[size(nums)];
constructSegmentTree(nums, 0, 0, nums.length-1);
return constructMaximumBinaryTree(nums, 0, nums.length-1);
}

private TreeNode constructMaximumBinaryTree(int[] nums, int low, int high) {
if (low > high)
return null;

int maxIndex = getMaxIndex(nums, low, high);
TreeNode node = new TreeNode(nums[maxIndex]);
node.left = constructMaximumBinaryTree(nums, low, maxIndex-1);
node.right = constructMaximumBinaryTree(nums, maxIndex+1, high);
return node;

}

private int constructSegmentTree(int[] nums, int index, int low, int high) {
if (low > high)
return -1;

if (low == high) {
segment[index] = low;
return low;
} else {
int mid = (low + high) >>> 1;
int left = constructSegmentTree(nums, 2*index+1, low, mid);
int right = constructSegmentTree(nums, 2*index+2, mid+1, high);
int maxIndex = -1;

if (left != -1 && right != -1) {
maxIndex = nums[left] < nums[right] ? right : left;
} else if (left != -1) {
maxIndex = left;
} else if (right != -1) {
maxIndex = right;
}

segment[index] = maxIndex;
return maxIndex;
}
}

private int getMaxIndex(int nums[], int a, int b) {
return getMaxIndexUsingSegmentTree(nums, 0, 0, nums.length-1, a, b);
}

private int getMaxIndexUsingSegmentTree(int[] nums, int index, int low, int high, int a, int b) {
if (low > high)
return -1;

if (high < a || low > b)
return -1;

if (low >= a && high <= b)
return segment[index];

int mid = (low + high) >>> 1;

int left = getMaxIndexUsingSegmentTree(nums, 2*index+1, low, mid, a, b);
int right = getMaxIndexUsingSegmentTree(nums, 2*index+2, mid+1, high, a, b);

int maxIndex = -1;

if (left != -1 && right != -1) {
maxIndex = nums[left] < nums[right] ? right : left;
} else if (left != -1) {
maxIndex = left;
} else if (right != -1) {
maxIndex = right;
}
return maxIndex;
}

private int size(int nums[]) {
int height = (int) Math.ceil(Math.log(nums.length)/Math.log(2));
return (int) (2*Math.pow(2, height) - 1);
}

}

``````

• Came up with a combination of iteration and recursion for a simple solution that beats all run times currently :)

public class Solution {
public TreeNode ConstructMaximumBinaryTree(int[] nums) {

``````    var currentMaxRoot = new TreeNode(nums[0]);

for(int i = 1; i < nums.Length; i++)
{
{
}
else
{
}

}

return currentMaxRoot;
}

{
if(currentRoot.right == null )
{
return;
}

{
}
else
{
return;
}
}
``````

}

• Most confusing and not explained at all question, after looking at solution question makes sense

• ``````public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums.length == 0) {
return null;
}
int index = 0;
int max = nums[0];
for(int i=1; i<nums.length; i++) {
if (max < nums[i]) {
max = nums[i];
index = i;
}
}
TreeNode node = new TreeNode(max);

node.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, index));
node.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, index + 1, nums.length));
return node;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.