             self[handle].payload = n.payload
             // Note that the above doesn't change root, leftmost, rightmost.
             // The reduction will be updated on the way up.
-            return _remove(next, keeping: handle)
+            let handle = _remove(next, keeping: handle)
+            return (handle, node.payload)
         }
         else {
-            return _remove(handle, keeping: successor)
+            let handle = _remove(handle, keeping: successor)
+            return (handle, node.payload)
         }
     }
 

    /// - Returns: The handle of the node that used to follow the removed node in the original tree, or nil if 
    ///   `handle` was at the rightmost position.
    /// - Complexity: O(log(count))
    public mutating func removeAndReturnSuccessor(handle: Handle) -> Handle? {
        return _remove(handle, successor: successor(handle))
    }


        return Config.compare(key, to: self[handle].head, reducedPrefix: reduction)
    }

    /// - Note: This can be faster than finding the old node and inserting if not found.
    public mutating func setPayloadOf(key: Key, to payload: Payload) -> (Handle, Payload?) {
        var slot: Slot = .Root
        var handle: Handle? = nil
        self.find(key) { h, m in
            switch m {
            case .Before:
                slot = .Toward(.Left, under: h)
                return .Before
            case .Matching:
                handle = h
                return .Matching
            case .After:
                slot = .Toward(.Right, under: h)
                return .After
            }
        }

        if let handle = handle {
            let old = setPayloadAt(handle, to: payload)
            return (handle, old)
        }
        else {
            let handle = insert(key, payload: payload, into: slot)
            return (handle, nil)
        }
    }

    public mutating func insert(key: Key, payload: Payload) -> Handle {
        func insertionSlotOf(key: Key) -> Slot {
