• Explanation: For the tree [1, 2, 3, 4, null, 5, 6, null, null, 7], the last row is at the fourth level, and the leftmost value is 7.
Approach: The approach is to use level order traversal (breadth-first search) to traverse the tree and capture the leftmost value in the last row.
Observations:
• Level order traversal is ideal for this problem, as it processes nodes row by row.
• We can use a queue to manage the nodes at each level.
• The leftmost value in the last row is always the first node encountered at the deepest level.
Steps:
• 1. Initialize a queue to store nodes for level order traversal.
• 2. While the queue is not empty, process nodes at the current level.
• 3. For each level, record the first node's value as the result.
• 4. Continue processing until all levels are covered.
• 5. Return the value of the first node of the last level.
Empty Inputs:
• The tree will not be empty, as the problem guarantees at least one node.
Large Inputs:
• The approach efficiently handles up to 10^4 nodes with a time complexity of O(n).
Special Values:
• A tree with only one node should return that node's value.
Constraints:
• Ensure the tree is traversed level by level without skipping any levels.
intfindBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int res = q.front()->val;
while(!q.empty()) {
int sz = q.size();
res = q.front()->val;
while(sz-->0) {
root = q.front();
q.pop();
if(root->left) q.push(root->left);
if(root->right) q.push(root->right);
}
}
return res;
}
1 : Function Definition
intfindBottomLeftValue(TreeNode* root) {
Defines the `findBottomLeftValue` function that takes a pointer to the root of a binary tree and returns the bottom-leftmost value.
2 : Queue Initialization
queue<TreeNode*> q;
Declares a queue `q` to perform a breadth-first traversal of the tree.
3 : Push Root to Queue
q.push(root);
Pushes the root node of the tree into the queue to start the BFS.
4 : Initialize Result
int res = q.front()->val;
Initializes `res` to store the value of the first node in the queue (i.e., the root node's value). This will be updated as we traverse the tree.
5 : BFS Loop Start
while(!q.empty()) {
Starts a while loop that continues as long as the queue is not empty, ensuring all tree nodes are processed.
6 : Queue Size Calculation
int sz = q.size();
Calculates the number of nodes at the current level by checking the size of the queue.
7 : Update Result
res = q.front()->val;
Updates `res` to the value of the leftmost node at the current level.
8 : Level Traversal Loop
while(sz-->0) {
Begins an inner loop to process all nodes at the current level.
9 : Process Current Node
root = q.front();
Assigns the front node of the queue to `root` for further processing.
10 : Pop Node from Queue
q.pop();
Removes the front node from the queue after processing it.
11 : Push Left Child
if(root->left) q.push(root->left);
Pushes the left child of the current node to the queue if it exists.
12 : Push Right Child
if(root->right) q.push(root->right);
Pushes the right child of the current node to the queue if it exists.
13 : Return Result
return res;
Returns the value stored in `res`, which is the bottom-leftmost node's value.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) where n is the number of nodes in the tree, as we traverse each node exactly once.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) in the worst case due to the queue storing nodes at the current level. In the best case (a skewed tree), the space complexity is O(1).
