We merge 2 trees into one. Note: all left tree's values must be less than all right tree's
(left: Node | None, right: Node | None)
| 59 | |
| 60 | |
| 61 | def merge(left: Node | None, right: Node | None) -> Node | None: |
| 62 | """ |
| 63 | We merge 2 trees into one. |
| 64 | Note: all left tree's values must be less than all right tree's |
| 65 | """ |
| 66 | if (not left) or (not right): # If one node is None, return the other |
| 67 | return left or right |
| 68 | elif left.prior < right.prior: |
| 69 | """ |
| 70 | Left will be root because it has more priority |
| 71 | Now we need to merge left's right son and right tree |
| 72 | """ |
| 73 | left.right = merge(left.right, right) |
| 74 | return left |
| 75 | else: |
| 76 | """ |
| 77 | Symmetric as well |
| 78 | """ |
| 79 | right.left = merge(left, right.left) |
| 80 | return right |
| 81 | |
| 82 | |
| 83 | def insert(root: Node | None, value: int) -> Node | None: |