Maximum Binary Tree - Practice Coding Problems

Maximum Binary Tree - Problem

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

1. Create a root node whose value is the maximum value in nums.

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.

Return the maximum binary tree built from nums.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,2,1,6,0,5]

› Output: [6,3,5,null,2,0,null,null,1]

💡 Note: Maximum element 6 becomes root. Left subtree built from [3,2,1] with root 3, right subtree from [0,5] with root 5.

Example 2 — Single Element

$ Input: nums = [3]

› Output: [3]

💡 Note: Single element forms a tree with just the root node.

Example 3 — Sorted Array

$ Input: nums = [1,2,3,4]

› Output: [4,null,3,null,2,null,1]

💡 Note: Maximum is always the rightmost element, creating a right-skewed tree.

Constraints

1 ≤ nums.length ≤ 1000
All integers in nums are unique
0 ≤ nums[i] ≤ 5000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [3,2,1,6,0,5] with no duplicates

Find Maximum

6 is maximum, becomes root with left=[3,2,1], right=[0,5]

Tree Structure

Recursively apply same rule to build complete tree

Key Takeaway

🎯 Key Insight: The largest element in any range becomes the parent of elements on its left and right

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is that each element becomes the root of its subtree by being the maximum in its range. The optimal approach uses a monotonic stack to build the tree in a single pass. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack	O(n)	O(n)	Use stack to maintain decreasing elements and build tree in one pass
Recursive Divide and Conquer	O(n²)	O(n)	Find max element, recursively build left and right subtrees

Monotonic Stack — Algorithm Steps

Traverse array from left to right
Maintain stack of nodes in decreasing order
When current > stack top, pop and make connections
Push current node to stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Push to Stack

Add nodes to stack in decreasing order

Pop and Connect

When larger element found, pop smaller ones and connect

Build Tree

Stack operations automatically create tree structure

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* solution(int* nums, int numsSize) {
    if (numsSize == 0) return NULL;
    
    struct TreeNode* stack[1000];
    int top = -1;
    
    for (int i = 0; i < numsSize; i++) {
        struct TreeNode* node = createNode(nums[i]);
        
        // Pop smaller elements and make them left children
        struct TreeNode* last = NULL;
        while (top >= 0 && stack[top]->val < nums[i]) {
            last = stack[top--];
        }
        
        // The last popped node becomes left child
        if (last) {
            node->left = last;
        }
        
        // If stack not empty, current becomes right child of top
        if (top >= 0) {
            stack[top]->right = node;
        }
        
        stack[++top] = node;
    }
    
    // Return the bottom element (root)
    return stack[0];
}

void printTreeArray(struct TreeNode* root) {
    if (!root) {
        printf("[]");
        return;
    }
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    int values[1000];
    int hasValue[1000];
    int count = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        
        if (node) {
            values[count] = node->val;
            hasValue[count] = 1;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        } else {
            values[count] = 0;
            hasValue[count] = 0;
        }
        count++;
    }
    
    // Remove trailing nulls
    while (count > 0 && !hasValue[count - 1]) {
        count--;
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        if (hasValue[i]) {
            printf("%d", values[i]);
        } else {
            printf("null");
        }
        if (i < count - 1) printf(",");
    }
    printf("]\n");
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    struct TreeNode* result = solution(nums, size);
    printTreeArray(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each element pushed and popped at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n nodes in worst case plus tree storage

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler