mergeLeavesWithCommonValues.ts

interface TrieNode {
  children?: { [key: string]: TrieNode }
  value?: string
}

function mergeLeavesWithCommonValues(node: TrieNode) {
  if (!node.children) {
    return;
  }
  for (const child of Object.values(node.children)) {
    mergeLeavesWithCommonValues(child)
  }

  const newChildren: Record<string, TrieNode> = {};
  const keysByValue: Record<string, string[]> = {};

  for (const [key, child] of Object.entries(node.children)) {
    if (child.value) {
      keysByValue[child.value] ??= [];
      keysByValue[child.value].push(key)
    } else {
      newChildren[key] = child;
    }
  }

  for (const [value, keys] of Object.entries(keysByValue)) {
    newChildren[keys.join("")] = { value };
  }
  node.children = newChildren;
}