O(1) algorithm to determine if node is descendant of another node in a multiway tree?

Представьте себе следующее дерево:

    A
   / \
  B   C
 / \   \
D   E   F

Я ищу способ узнать, является ли, например, F потомком A (примечание: F не обязательно должен быть прямым потомком A), что в данном конкретном случае быть правдой. Только ограниченное количество потенциальных родительских узлов необходимо протестировать против большего пула потенциальных потомков.

При проверке того, является ли узел потомком узла в потенциальном родительском пуле, его необходимо протестировать на ВСЕХ потенциальных родительских узлах. .

Это то, что придумал a:

• Преобразование многостороннего дерева в дерево, т.е. присвоение следующих префиксов каждому узлу в приведенном выше дереве:

    A = 1
   В = 11
   С = 12
   D = 111
   E = 112
   F = 121
  

• Then, reserve a bit array for every possible prefix size and add the parent nodes to be tested against, i.e. if C is added to the potential parent node pool, do:

   1 2 3 <- Prefix length
  
  *[1] [1] ...
   [2] *[2] ...
   [3] [3] ...
   [4] [4] ...
   ... ...
  

• When testing if a node is a descendant of a potential parent node, take its trie prefix, lookup the first character in the first "prefix array" (see above) and if it is present, lookup the second prefix character in the second "prefix array" and so on, i.e. testing F leads to:

   F = 1 2 1
  
   *[1] [1] ...
   [2] *[2] ...
   [3] [3] ...
   [4] [4] ...
   ... ...
  

  so yes F, is a descendant of C.

This test seems to be worst case O(n), where n = maximum prefix length = maximum tree depth, so its worst case is exactly equal to the obvious way of just going up the tree and comparing nodes. However, this performs much better if the tested node is near the bottom of the tree and the potential parent node is somewhere at the top. Combining both algorithms would mitigate both worst case scenarios. However, memory overhead is a concern.

Is there another way for doing that? Any pointers greatly appreciated!