Build a weighted binary tree from character counts

Given a string s of letters ('A'-'Z', 'a'-'z'; case matters), build a binary tree that summarizes how often each character appears.

Each node has three fields: ch, count, and two child pointers.

Rules for a valid tree

• Leaves. Every distinct character of s is a leaf exactly once. The leaf's ch is the character and its count is how many times it appears in s.
• Internal nodes. Every non-leaf node has ch = '#', exactly two children, and count equal to the sum of the counts of all leaves under it.

Goal. Among all valid trees, return one with the smallest total weighted depth:

cost = sum over leaves of (leaf.count * depth(leaf))   # the root has depth 0

so characters that occur often sit close to the root.

Implement:

def build_tree(s: str) -> Node | None

Return None for an empty string. If s has one distinct character, the root is that leaf.

Constraints: 0 <= len(s) <= 10^6. Any optimal tree is accepted when counts tie.

Example 1

s = "mmmmmmxxyz" -> counts m:6, x:2, y:1, z:1.

One optimal tree:

          #(10)
         /     \
      m(6)     #(4)
              /    \
           x(2)    #(2)
                  /    \
               y(1)    z(1)

Cost = 6*1 + 2*2 + 1*3 + 1*3 = 16.

Example 2

s = "pqrs" -> all counts are 1. A balanced tree puts every leaf at depth 2, cost 8. A chain such as p at depth 1, q at depth 2, r and s at depth 3 is valid but costs 9, so it is not accepted.

Possible follow-ups: produce a bit code per character and decode a bit string with the tree; serialize the tree; build in O(k) when the counts arrive sorted.

Reconstructed from the reported question; details may differ from what interviewers ask.