654.maximum-binary-tree.md

654. Maximum Binary Tree

Given an arraay nums, construct a maximum binary tree where:

• The root is the maximum number.
• The left subtree is construcuted from the elements left to the max, that is nums[0..i-1].
• The right subtree is construcuted from the elements right to the max, that is nums[i+1..n-1].

nums = [3,2,1,6,0,5]

// Construct the tree:
        6
      /   \
[3,2,1]   [0,5]

DFS

fun constructMaximumBinaryTree(nums: IntArray): TreeNode? {
    return construct(nums, 0, nums.size - 1)
}

private fun construct(nums: IntArray, start: Int, end: Int): TreeNode? {
    if (start > end) return null
    var max = nums[start]
    var maxIndex = start
    for (i in (start + 1)..end) {
        if (max < nums[i]) {
            max = nums[i]
            maxIndex = i
        }
    }
    val root = TreeNode(max)
    root.left = construct(nums, start, maxIndex - 1)
    root.right = construct(nums, maxIndex + 1, end)
    return root
}

• Time Complexity: O(n^2), for each construct call, we need to iterate through the array to find the maximum value, which takes O(n) time. Then we recursively call construct for the left and right subtrees, which takes O(n) time in worst case. Total time complexity is O(n^2).
• Space Complexity: O(n), the recursion stack takes O(n) space.

Worst case:

[1, 2, 3]

// Skewed tree
      3
     /
    2
   /
  1

We have to scan

• [1, 2, 3]: n times
• [1, 2]: n-1 times
• [1]: n-2 times

Total n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 times.

Monotonic Stack

We can use a monotonic decreasing stack to construct the tree:

• Stack always keeps all possible left children of the max node.
• Pop the nodes are smaller, and become left child of current node when we find a larger node. (stack.last() < num)
• If the stack is not empty, the current node is the right child of the previous node in stack.

fun constructMaximumBinaryTree(nums: IntArray): TreeNode? {
    val stack = ArrayDeque<TreeNode>()
    for (num in nums) {
        val node = TreeNode(num)
        while (stack.isNotEmpty() && stack.last().`val` < num) {
            // We will keep assigning left child of the larger node to the smaller node in stack
            node.left = stack.removeLast()
        }
        // The current node is the right child of previous node in stack
        if (stack.isNotEmpty()) {
            stack.last().right = node
        }
        stack.addLast(node)
    }
    return stack.first()
}

• Time Complexity: O(n), we iterate through the array once, and for each element, we only push it onto the stack once and pop it at most once.
• Space Complexity: O(n), the stack takes O(n) space.

Dry Run

There is a very nice visualization of the process.

For nums = [3,2,1,6,0]:

// Iterate 2:
nums = [3, 2, 1, 6, 0] 
           i
stack = [3] 
stack.last().right <- 2
tree = 
3
  \ 
    2
stack = [3, 2]

// Iterate 1:
nums = [3, 2, 1, 6, 0] 
              i
stack = [3, 2] 
stack.last().right <- 1
tree = 
3
  \ 
    2
      \
       1
stack = [3, 2, 1]

// --------------------------------
// Iterate 6:
nums = [3, 2, 1, 6, 0] 
                 i
stack = [3, 2, 1] < 6
// execute while loop
6.left <- 1
tree =
3
  \ 
    2    6
      \ / 
       1
stack = [3, 2] < 6
// execute while loop
6.left <- 2
tree =
3      6
  \   / 
    2   
      \ 
       1
stack = [3] < 6
// execute while loop
6.left = 3
tree =
   6
 /
3     
  \   
    2   
      \ 
       1
stack = [6]

// --------------------------------
// Iterate 0:
nums = [3, 2, 1, 6, 0] 
                    i
stack = [6]
stack.last().right <- 0
tree =
   6
 /   \
3     0 
  \   
    2   
      \ 
       1
stack = [6, 0]

// --------------------------------
// End of iteration:
return stack.first() = 6