Show problems as
Classic problem #701MediumTreeBinary Search TreeBinary Tree

Insert into a Binary Search Tree

Real-world version: Threading a Weight Onto the Parcel Rack
Tracked in this browser only
Read Insert into a Binary Search Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A depot hangs its parcel weight cards on a rack shaped as a search tree. Every card has a lighter peg and a heavier peg below it. All weights hanging anywhere below a card's lighter peg are strictly smaller than that card's weight, and all weights hanging anywhere below its heavier peg are strictly larger. All weights on the rack are distinct.

A new card of weight weight arrives, and it is guaranteed that no card on the rack already carries that weight. Thread it in the way the depot always does: start at the top card and, at each card, move to its lighter peg when the new weight is smaller and to its heavier peg when the new weight is larger. The first time that peg is empty, hang the new card there. No existing card may be moved, re-hung or re-weighed.

How a rack is written down. Both tree and the value you return use the same flat listing. Put the top card into a waiting line on its own. Then repeatedly take the front of the line: write its weight at the end of the listing, and add to the back of the line whatever hangs on its lighter peg and then whatever hangs on its heavier peg, adding the marker null for an empty peg. When null reaches the front of the line, write null to the listing and add nothing. Stop when the line runs dry, then delete any null entries sitting after the last weight. An empty rack is written as the empty list [].

Return the listing of the rack after the new card has been threaded in.

Examples

Example 1

Input
tree = [50, 30, 70], weight = 60
Output
[50, 30, 70, null, null, 60]

60 is heavier than 50 and lighter than 70, so it ends up on the lighter peg of the card holding 70. The two empty pegs under 30 keep their `null` markers because a weight is written after them.

Example 2

Input
tree = [], weight = 40
Output
[40]

The rack is bare, so the new card becomes the top card and the listing holds nothing else.

Example 3

Input
tree = [10, null, 20, null, 30], weight = 25
Output
[10, null, 20, null, 30, 25]

Each card on this rack hangs from a heavier peg. The walk passes 10 and 20, then stops at the lighter peg of the card holding 30.

Constraints

  • The number of cards on the rack is in the range [0, 10^4].
  • -10^8 <= card weight <= 10^8
  • All card weights are distinct.
  • -10^8 <= weight <= 10^8
  • weight is guaranteed not to be on the rack already.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def thread_in_weight(tree: list, weight: int) -> list:
Java
public List<Integer> threadInWeight(List<Integer> tree, int weight)

More on the same topics