Other implementations of trees, Apart from the linked structure of the tree implementation, we can build the following as well.

1. HashMap, that groups the linked structures. It takes a key, do a modular to map the hash values (e.g. SHA256) to a specific group, then add the node in that linked structure. When searching, follow the similar procedure to access the group and then the tree node. This can reduce the search time.

2. LinkedTreeMap stays ordered and sorted. But an iterator is hard to implement with this structure. So what people do it to maintain a separate linked list to simultaneously work with the tree. Each tree node will have key, value, left, right and next attributes.

Resources

• Hash Map
• Linked Tree Map
• Word count using lined tree map

One thing that takes a long time for me to debug is the “word count". An character array was used to repeatedly read in the word and be pushed to the tree. However, while building the root of the tree, we made the root a pointer equals to this character array pointer. Therefore, the root is constantly changing its content while reading the new word, which leads to a bug. Specifically, we did.

    char *copy = malloc(4 * sizeof(char));
    strcpy(copy, key);
    new->key = copy;