How to increment height of each path in a suffix trie

Question

I have created a suffix trie and I am trying to find a way to accumulate and store its height in the reverse order and store it in each node. Example:

with strings ['abcd', 'abc', 'aa']

So I have implemented this in two classes. 1 is the Node class and 2 is the Trie class, and each vertex is a node, and hence to represent each of the height would be to go to each vertex and retrieve

ex. a.height = 4, b.height = 3, c.height = 2 instead of the normal (easy) a.height = 1, b.height = 2, c.height = 3

The nodes doesn't have to be the same height away from the root node and the $ sigh represents the end of a string. The height is added up from the bottom ($) as indicated from the image

I have been able to store the frequency of how often each character gets repeated in the Trie by simply initializing in the class Trienode -> self.freq = 1 and updating it during insert. But this is not the height and I'm out of ideas. Any suggestions would be welcome.

Here's my code without the frequency update:

class TrieNode:
 
# Trie node class
def __init__(self):
    self.children = [None]*26

    # isEndOfWord is True if node represent the end of the word
    self.isEndOfWord = False

class Trie:
 
# Trie data structure class
def __init__(self):
    self.root = self.getNode()

def getNode(self):
 
    # Returns new trie node (initialized to NULLs)
    return TrieNode()

def _charToIndex(self,ch):
     
    # private helper function
    # Converts key current character into index
    # use only 'a' through 'z' and lower case
     
    return ord(ch)-ord('a')


def insert(self,key):
     
    # If not present, inserts key into trie
    # If the key is prefix of trie node,
    # just marks leaf node
    pCrawl = self.root
    length = len(key)
    for level in range(length):
        index = self._charToIndex(key[level])

        # if current character is not present
        if not pCrawl.children[index]:
            pCrawl.children[index] = self.getNode()
        pCrawl = pCrawl.children[index]

    # mark last node as leaf
    pCrawl.isEndOfWord = True

Thanks

user_6740515 · Answer

Doing this recursively is probably the best way. You'll need to update your TrieNode class to include a 'height' attribute for this.

def compute_heights(self, node=None):
  if not node: node = self.root  # Default value

  # Base case: If we have found an end, return 0 as the height.
  if node.isEndOfWord:
    return 0

  max_so_far = 0  # Use this to track the maximum height among all children

  # Iterate over all children
  for child in node.children:
    self.compute_heights(child)  # Recursively compute height
    max_so_far = max(max_so_far, child.height)
  
  node.height = 1 + max_so_far  # Update the current node's height

You can simply call this function on an instance, the node value is set to the root if none is provided. The function can also be modified to return the height of the node it is called on.

You can run this after completely defining a trie. To allow insertions and update these values live, you will need to search upwards from the newly-created node for which you will probably need to keep track of each node's parent. With that, you can iteratively check at each step on the way from the inserted leaf to the root if the height needs to be updated.

How to increment height of each path in a suffix trie

1 Answers