Sponsored
Sponsored
In this approach, we utilize depth-first search to explore each path from the leaf to the root. We maintain the current path in a string, which is reversed each time we reach a leaf node. We then compare it to the currently known smallest string, updating the smallest string if the new path is smaller.
Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
1#include <string.h>
2#include <limits.h>
3
4void dfs(TreeNode* node, char* path, char* smallest, int pathLen) {
5 if (!node) return;
6 path[pathLen++] = node->val + 'a';
7 path[pathLen] = '\0';
8 if (!node->left && !node->right) {
9 if (strcmp(path, smallest) < 0) strcpy(smallest, path);
10 }
11 dfs(node->left, path, smallest, pathLen);
12 dfs(node->right, path, smallest, pathLen);
13 pathLen--;
14}
15
16char* smallestFromLeaf(TreeNode* root) {
17 char* smallest = (char*)malloc(8500);
18 memset(smallest, '~', 8500);
19 char path[8500];
20 dfs(root, path, smallest, 0);
21 return strdup(smallest);
22}In this C approach, manual memory management is performed with the use of arrays and characteristic C libraries. The DFS method traverses the tree, forming strings of characters representing node values as it goes. The `smallest` string is updated whenever a leaf node that results in a smaller path is found. Care is given to the manual handling of string operations and memory allocations.