Huffman-Style Binary Encode / Decode

Build binary encodings for characters by constructing a frequency tree, then implement both encode and decode. The prompt is long and conceptually close to Huffman coding, with the main challenge being understanding the tree construction rules. Requirements Given a string, implement two functions: encode(s) — convert the input string into its binary representation. decode(bits) — recover the original string from the encoded binary representation. The encoding is built from character frequencies: Start from characters as leaf nodes. Build a binary tree from lower-frequency characters upward. A parent node's frequency is the sum of its two children. Edge values are 0 and 1. For each character, traverse from root to leaf and collect edge values; the resulting bit path is that character's binary representation. More frequent characters should end up with shorter binary representations. Notes The exact tie-breaking and tree-construction order were described as prompt-specific and lengthy. Clarify tie-breaking before coding; it determines whether decode can match the expected encoding exactly. The candidate only completed encode, so the community-visible prompt is not fully validated end to end. The core structure is a frequency map, priority queue or sorted leaf list, tree nodes, a DFS codebook pass, and a trie/tree traversal for decoding. Preparation Implement canonical Huffman coding from scratch: frequency count, min-heap, tree construction, codebook DFS, encode, and decode. Practice explaining why prefix-free codes make decoding unambiguous. Drill tie-break handling in heap entries so output is deterministic under equal frequencies.