Maximum Binary Tree II — LeetCode 998 Python Solution

The problem

A maximum tree is a tree where every node has a value greater than any other value in its subtree. You are given the root of a maximum binary tree and an integer val.

Example

Input

root = [4,1,3,null,null,2], val = 5

Output

[5,4,null,1,3,null,null,2]

Explanation

a = [1,4,2,3], b = [1,4,2,3,5]

Python solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoMaxTree(
        self, root: Optional[TreeNode], val: int
    ) -> Optional[TreeNode]:
        if root is None or root.val < val:
            return TreeNode(val, root)
        root.right = self.insertIntoMaxTree(root.right, val)
        return root

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 998. Maximum Binary Tree II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Tree and Binary Tree.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems