The tree is a search tree with distinct keys: for every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write add_key(root, key) -> TreeNode: add key, which is not in the tree yet, as a new leaf, without moving any existing node. There is exactly one spot where a new leaf keeps the ordering intact. Return the root of the tree (for an empty tree that is the new node).
# 8 8
# / \ / \
# 3 12 -> 3 12
# / \ / \
# 1 6 1 6
# \
# 7
add_key(root, 7) # the tree on the right
add_key(None, 5) # a single node 5
- Up to 70,000 nodes, at most 500 levels deep. Keys are distinct integers between
-10^9and10^9. - Aim for O(h), where
his the height of the tree. The tests count how many nodes you look at.
Show hint
Compare the key with the current node to decide which side it belongs on, and keep going until that side is empty.