Maximum Binary Tree II

Problem Id: 998 Difficulty: Medium Tag: Tree


We could search the position of the inserting value by following steps going from root node.

  1. If the current node is None, then insert the new node here.
  2. If the current node is greater than the value, then the new node must be on the right sub-tree of the node.
  3. If the current node is smaller than the value, then the current sub-tree should be set to the left sub-tree of the new node and the new node should be inserted into here.


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode:
        head = TreeNode(float('inf'))
        head.right = root
        new = TreeNode(val)
        current = head.right
        parent = head
        while True:
            if current is None:
                parent.right = new
            elif current.val > val:
                parent, current = current, current.right
                new.left = parent.right
                parent.right = new
        return head.right