Implementation

We build BST insert and search plus a min-heap in Python, then port the min-heap to C++, Java and TypeScript.

Python: binary search tree

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None


class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            return
        cur = self.root
        while True:
            if key == cur.key:
                return                      # ignore duplicates
            side = "left" if key < cur.key else "right"
            nxt = getattr(cur, side)
            if nxt is None:
                setattr(cur, side, Node(key))
                return
            cur = nxt

    def contains(self, key):
        cur = self.root
        while cur is not None and cur.key != key:
            cur = cur.left if key < cur.key else cur.right
        return cur is not None


t = BST()
for k in [50, 30, 70, 20, 40]:
    t.insert(k)
print(t.contains(40), t.contains(45))  # True False

• Loops, not recursion, so a degenerate tree cannot hit the recursion limit.
• side picks a child; an empty slot gets the new node, otherwise we move down.

Python: min-heap

class MinHeap:
    def __init__(self, items=()):
        self.a = list(items)
        for i in range(len(self.a) // 2 - 1, -1, -1):  # heapify, O(n)
            self._down(i)

    def push(self, x):
        self.a.append(x)
        self._up(len(self.a) - 1)

    def peek(self):
        return self.a[0]

    def pop(self):
        a = self.a
        top, last = a[0], a.pop()   # IndexError when empty
        if a:
            a[0] = last
            self._down(0)
        return top

    def _up(self, i):
        a = self.a
        while i > 0 and a[i] < a[(i - 1) // 2]:
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p

    def _down(self, i):
        a, n = self.a, len(self.a)
        while (c := 2 * i + 1) < n:
            if c + 1 < n and a[c + 1] < a[c]:
                c += 1              # the smaller child
            if a[i] <= a[c]:
                break
            a[i], a[c] = a[c], a[i]
            i = c

    def __len__(self):
        return len(self.a)


h = MinHeap([9, 5, 7, 1, 3, 2])
h.push(4)
print([h.pop() for _ in range(len(h))])  # [1, 2, 3, 4, 5, 7, 9]

• _up climbs while smaller than the parent (i - 1) // 2.
• pop moves the last item to the root, then calls _down.
• _down runs while a left child 2 * i + 1 exists and swaps with the smaller child.

C++

#include <iostream>
#include <utility>
#include <vector>

class MinHeap {
    std::vector<int> a;
public:
    void push(int x) {
        a.push_back(x);
        std::size_t i = a.size() - 1;
        while (i > 0 && a[i] < a[(i - 1) / 2]) {
            std::swap(a[i], a[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }
    int pop() {  // call only when not empty
        int top = a.front();
        a.front() = a.back();
        a.pop_back();
        std::size_t i = 0, n = a.size();
        while (2 * i + 1 < n) {
            std::size_t c = 2 * i + 1;
            if (c + 1 < n && a[c + 1] < a[c]) ++c;
            if (a[i] <= a[c]) break;
            std::swap(a[i], a[c]);
            i = c;
        }
        return top;
    }
    bool empty() const { return a.empty(); }
};

int main() {
    MinHeap h;
    for (int x : {5, 3, 8, 1, 9, 2}) h.push(x);
    while (!h.empty()) std::cout << h.pop() << ' ';  // 1 2 3 5 8 9
}