SeniorCodeRareNot answered yet
Find two subtrees with the same set of letters in O(N)
Each node of a binary tree holds one letter A–Z. Two nodes are equivalent if the sets of letters in their subtrees are identical (set semantics, frequencies ignored). Return any two distinct equivalent nodes, or null pointers if none exist.
Requirements:
- O(N) time over the N-node tree.
- The 26-letter alphabet fits a 32-bit mask, so a subtree's letter set is the OR of its children's masks.
struct TNode { char Value; TNode* Left; TNode* Right; };
std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root) {
// your code here
}Write the implementation.
Post-order recursion: a node's letter set is (1 << (Value-'A')) OR-ed with the masks of its children. Store each computed mask in a hash map from mask to node; the first time a mask repeats you have two equivalent subtrees. One traversal, O(N) time and O(N) space.
- ✗Counting letter frequencies instead of treating the subtree as a set (the spec ignores frequencies)
- ✗Recomputing a subtree's mask from scratch at each node instead of OR-ing children's masks
- ✗Forgetting to seed the current node's own letter into its mask
- →How would you instead return the equivalent pair with the largest combined subtree size?
- →Why is a 32-bit integer enough, and when would you need a different descriptor?
Contents
Task
Each node holds a letter A–Z. Find two nodes whose subtrees contain the same set of letters.
Solution
uint32_t collect(TNode* node, std::unordered_map<uint32_t, TNode*>& seen,
std::pair<TNode*, TNode*>& found) {
if (!node) return 0;
uint32_t mask = 1u << (node->Value - 'A');
mask |= collect(node->Left, seen, found);
mask |= collect(node->Right, seen, found);
auto it = seen.find(mask);
if (it != seen.end() && !found.first) found = {it->second, node};
else seen.emplace(mask, node);
return mask;
}Key points
- The letter set is a bitmask; combining subtrees is an
ORof children's masks. - A
mask → nodehash map catches the first repeat in O(N). - Set semantics: frequencies do not matter, so the mask is exact.
Contents
