Sponsored
Sponsored
Using a BFS approach, we can efficiently explore each level of the tree from top to bottom. At each level, we keep track of the first value. The leftmost value in the last row will be the first value at the deepest level, which is the last processed level in BFS.
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) in the worst case, for the queue storing nodes at the deepest level.
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8} TreeNode;
9
10int findBottomLeftValue(TreeNode* root) {
11 TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * 10000);
12 int front = 0, rear = 0;
13 queue[rear++] = root;
14 TreeNode* node;
15 while (front < rear) {
16 node = queue[front++];
17 if (node->right) queue[rear++] = node->right;
18 if (node->left) queue[rear++] = node->left;
19 }
20 free(queue);
21 return node->val;
22}This C solution implements a BFS using a dynamically allocated array to simulate a queue. Nodes are enqueued right-to-left at each level, ensuring the last node processed is the leftmost at the deepest level.
For the DFS approach, we explore as deep as possible, preferring left subtrees over right. We track the maximum depth, updating the leftmost value encountered at each depth level. This ensures the leftmost node at the deepest level is found.
Time Complexity: O(n), as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursive call stack.
1#include
This C solution implements DFS via recursion, carrying along depth and maximal depth pointers, modifying leftmost value at maximum depth, favoring left traversals first.