explanation

Reasoning-
The solution uses recursion to handle infinite-depth lookup within directories.

Time-Complexity-

• The solution looks within each subdirectory and checks for each file, that means for n number of files, it grows through each file once. There are 3 assignment and 3 function call within each recursive call - O(6n)
• There are one assignment and one return call in find_files function. O(2)

Worst-Time-Complexity - O(6n+2)
Worst-Time-Complexity of order = 0(n)

Space Complexity -

• One recursive call which creates a function frame for each function call - O(n)
  • One output list for storing values of matched string - O(n)

Worst-Space-Complexity - O(2n)
Worst-Space-Complexity of order = 0(n)

Reasoning-
The solution uses:

• A hashmap to store frequencies of characters since it allows constant time get and put operations.
• A sorted list of Tuppels which acts as a priority queue so the last 2 number can feed the Huffman tree, Another approach could have been to use actual priority queue but there was some issue implementing it so I used sorted Tupples as suggested in the description of the problem.
  • A tree to implement Huffman encoding
  • Two maps to store character to binary representation and vice versa to fast look for encoding and decoding.

Time-Complexity-

• Iterate the string and creates Hashmap for frequency - O(n)
• Create string to Tupple list - O(n)
• Create Tree from Tupples and sort tupple - O(n)*nlog(n) = n²log(n)
• Create a character to binary map - O(n)

Worst-Time-Complexity - O(6n+2)
Worst-Time-Complexity of order = 0(n)

Space Complexity -

• One recursive call which creates a function frame for each function call - O(n)
  • One output list for storing values of matched string - O(n)

Worst-Space-Complexity - O(2n)
Worst-Space-Complexity of order = 0(n)