Complexity

A heap is weak at finding an arbitrary value (it may have to scan everything) and strong when only the minimum matters. A BST gives O(log n) across the board but has larger constant factors and more memory per element.

Cost of traversals

Every traversal visits each node once, so time is O(n). The extra space is the size of the recursion stack or explicit stack: O(h) for depth-first traversals, and for level-order the width of the widest level (about n/2 in a complete tree). In a degenerate tree h approaches n and recursion can exceed Python's limit, so it pays to know the iterative version with an explicit stack.

def inorder_iter(root):
    out, stack, cur = [], [], root
    while stack or cur:
        while cur:                 # go left as far as possible, stacking nodes
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.key)
        cur = cur.right
    return out


root = None
for k in range(5000):              # degenerate tree of height 4999
    root = insert(root, k)
print(len(inorder_iter(root)))     # 5000, no recursion limit issue

Why heapify is O(n)

Heapify moves a node of height k down at most k levels. A complete binary tree has about n / 2^(k+1) nodes of height k, so the total work is n x (1/4 + 2/8 + 3/16 + ...), and that series converges to a constant (1). In other words, most nodes sit near the leaves and barely move. Pushing items one at a time, by contrast, can carry each new item all the way up, which costs O(n log n).

import heapq


class Counted:
    count = 0

    def __init__(self, v):
        self.v = v

    def __lt__(self, other):
        Counted.count += 1
        return self.v < other.v


data = list(range(100_000, 0, -1))   # descending: worst case for push

Counted.count = 0
heapq.heapify([Counted(v) for v in data])
print("heapify", Counted.count)      # about 150,000 (about 1.5n)

Counted.count = 0
h = []
for v in data:
    heapq.heappush(h, Counted(v))
print("n pushes", Counted.count)     # about 1,470,000 (on the order of n log n)

Compared with other structures

All of them use O(n) space, but a heap lives in a single array with no pointers and good memory locality, so it is fast in practice. A BST node carries two child pointers, and balanced trees add a height or colour field on top.

Summary

Height drives the cost of tree operations. A heap's shape is fixed as a complete binary tree, so insert and remove-min are always O(log n) and heapify is O(n). A BST is O(log n) on average but degrades to O(n) on sorted input, so use a balanced BST when the worst case matters. For deep trees, consider an explicit stack instead of recursion.