Deterministic Tree Encoding And Decoding

What's being tested

This tests deterministic Huffman-style coding: building a frequency-based binary tree, deriving prefix-free bit codes, and decoding by tree traversal. Interviewers probe whether you can implement priority-queue construction cleanly while preserving exact tie-breaking so encode/decode are reproducible.

Patterns & templates

• Frequency counting with dict / Counter — compute symbol weights in O(n) time; handle empty input and single-symbol alphabets explicitly.

• Min-heap tree construction using heapq — repeatedly pop two lowest-frequency nodes, merge, and push; total cost is O(k log k) for k symbols.

• Deterministic tie-breaking — heap entries need stable fields like (freq, min_symbol, sequence_id, node) because raw tree nodes are not comparable.

• Prefix-code generation via DFS — assign 0 for left, 1 for right; store char -> bitstring, with single-node trees using "0".

• Decoding by traversal — walk bits from root to leaf, emit symbol, reset to root; validate invalid bits and incomplete terminal paths.

• Round-trip testing with decode(encode(s)) == s — include ties, repeated characters, one unique character, empty string, and non-ASCII symbols.

Common pitfalls

• Pitfall: Ignoring tie-breaking creates different valid Huffman trees, causing hidden tests to fail despite correct compression logic.

• Pitfall: Forgetting the single-character case can produce an empty code, making encoded output ambiguous or undecodable.

• Pitfall: Comparing custom Node objects directly in heapq crashes when frequencies tie; include deterministic primitive fields before the node.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.