Problem Description

Implement a binary encoding and decoding scheme for strings, inspired by Huffman coding, that leverages character frequencies. You must provide two functions:

1. encode(s): Takes an input string s and returns a tuple containing the generated bitstring and the constructed encoding tree.
2. decode(bitstring, tree): Takes an encoded bitstring and the corresponding encoding tree, and reconstructs the original string.

Encoding Rules

Given an input string s:

1. Character Frequency Counting: Determine the frequency of each distinct character present in s.
2. Leaf Node Creation: For every distinct character, create a leaf node. The node's weight should be equal to its character's frequency.
3. Tree Construction: Build a binary tree by iteratively combining the two nodes with the smallest weights into a new parent node.
   • The parent node's weight is the sum of its two children's weights.
   • The two chosen nodes become the parent's left and right children.
4. Edge Labeling: Assign a label to each edge: 0 for the left child edge and 1 for the right child edge.
5. Character Code Generation: The binary representation (code) for a character is formed by concatenating the edge labels along the path from the root of the tree to that character's leaf node.
6. Bitstring Assembly: The final encoded bitstring is the concatenation of the individual codes for each character in the input string s, in their original order.

Determinism and Tie-breaking

To ensure a deterministic encoding when multiple nodes have identical weights, the following tie-breaking rule must be applied:

• When selecting the two minimum-weight nodes, candidates should be sorted by (weight, key).
• For a leaf node, its key is its character (using lexicographical order for comparison).
• For an internal node, its key is defined as the smallest character contained within its subtree.
• When attaching the two chosen nodes to a new parent, the node with the smaller (weight, key) pair must be assigned as the left child (receiving edge label 0).

Decoding Rules

Given an encoded bitstring and the encoding tree:

• Traverse the encoding tree starting from its root.
• Read bits from the bitstring sequentially from left to right.
• A 0 bit indicates a traversal to the left child; a 1 bit indicates a traversal to the right child.
• Upon reaching a leaf node, append its character to the decoded output string and then reset the traversal back to the root of the tree to process the next character's code.

Inputs and Outputs

• The input string s will consist of arbitrary ASCII characters.
• The encoded bitstring should be returned as a string composed solely of '0' and '1' characters.

Edge Cases

• If the input string s is empty, the encode function should return ("", null), and the decode function should return "".
• If s contains only one distinct character (e.g., "aaaa"), that character should be assigned the code "0". Consequently, encoding "aaaa" would result in "0000".

Constraints

• The length of the input string s will be between 0 and 2 * 10^5 characters, inclusive.
• The number of distinct characters (σ) in s will not exceed 256.
• The solution should aim for a time complexity of O(|s| + σ log σ) and an auxiliary space complexity of O(σ) (excluding the output bitstring).