513. Find Bottom Left Tree Value
Problem Description
The problem gives us a binary tree and asks us to find the leftmost value in the tree's last row. In simple terms, we need to go to the very bottom row of the tree and return the value of the node that is furthest to the left.
Flowchart Walkthrough
Let's navigate the algorithm using the flowchart. We'll move through it step-by-step to determine the most suitable algorithm for solving LeetCode problem 513. "Find Bottom Left Tree Value".
Is it a graph?
- Yes: Although the problem is directly about a tree (a type of graph), trees are indeed special cases of graphs.
Is it a tree?
- Yes: The problem explicitly mentions dealing with a binary tree.
Since it's determined to be a tree, the next appropriate algorithmic approach mentioned directly in the flowchart following the tree node is "DFS".
Conclusion: According to the flowchart, the next step after identifying the structure as a tree is to use Depth-First Search (DFS). This is effective for searching through tree structures where we need to explore depths, such as finding the bottom-most (deepest) and left-most node in this specific problem.
Intuition
To find the leftmost value in the last row, we can perform a breadth-first search (BFS) traversal of the tree. In BFS, we start with the root and explore all the nodes at the current depth level before moving on to the nodes at the next level. We can use a queue data structure to keep track of the nodes at the current level.
The BFS approach is useful here because it naturally visits levels from top to bottom, and for each level, from left to right. So, the last value we encounter at each level would be the leftmost value. When the queue no longer has nodes to process, the last node we looked at would be the leftmost node of the bottom row.
The intuition for this approach comes from understanding that the level order traversal will encounter all nodes level by level. We don't need to preserve the entire level; we only keep the last node processed (the leftmost of that level). We update this value as we proceed to the next level.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
Solution Approach
The solution to this problem uses a simple Breadth-First Search (BFS) algorithm. BFS is usually implemented using a queue data structure, which allows us to process nodes in a "first-in, first-out" (FIFO) order. In this solution, a deque
from the collections
module is used because it enables efficient append and pop operations from both ends of the queue.
Here is the step-by-step approach used in the solution:
-
Initialize a queue (in this case,
q
) with the root node of the binary tree. This queue will hold the nodes to be processed. -
Initialize a variable (
ans
) to keep track of the leftmost value. -
While the queue is not empty, perform the following steps:
- Update
ans
with the value of the first node in the queue (q[0].val
), as this is guaranteed to be the leftmost node of the current level. - Loop over the nodes at the current level, which is the current size of the queue.
- Remove the node from the front of the queue using
popleft()
. - If the node has a left child, append it to the queue. This ensures that the left child is processed before the right child.
- If the node has a right child, append it to the queue.
- Remove the node from the front of the queue using
- Update
-
After the last level has been processed, and the queue is empty,
ans
will hold the value of the leftmost node in the last row of the tree. -
Return the value stored in
ans
.
The BFS process ensures that we traverse the tree level by level, and by always taking the first element in the queue, we are guaranteed to process the leftmost node of each level. When we are at the last level, the first node in the queue will be the leftmost node of the bottommost level, which is what the problem asks us to return.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate this solution approach using a simple binary tree.
Suppose our binary tree looks like this:
1 / \ 2 3 / / \ 4 5 6 / 7
We want to find the leftmost value in the tree's last row. According to the tree above, the last row is the row with the nodes 4, 7, and 6, and the leftmost value is 4.
Let's apply the BFS algorithm step-by-step:
-
Initialize the queue with the root node (which is 1 in this case). Our queue (q) looks like this: [1]
-
Initialize the
ans
variable to keep track of the leftmost value. Currently,ans
is not set. -
The queue is not empty, so we start our while loop.
- Update
ans
with the value of the first node in the queue, which is 1 (q[0].val
). - There is only one node at this level, so we process it.
- We pop the node 1 using
popleft()
, leaving the queue empty. - Since node 1 has a left child (node 2), we append it to the queue. The queue now contains [2].
- Since node 1 also has a right child (node 3), we append it as well. The queue now contains [2, 3].
- We pop the node 1 using
- Update
-
We proceed with the next iteration of the while loop, since the queue is not empty. The queue currently has [2, 3].
- Update
ans
with the value of the first node in the queue, which is now 2. - There are two nodes at this level (2 and 3). We process these two nodes.
- Pop node 2 from the queue and check its children. It has one left child, node 4, which we append to the queue. Now the queue is [3, 4].
- Pop node 3, append its left child (node 5) and its right child (node 6) to the queue. The queue becomes [4, 5, 6].
- Update
-
After processing these nodes, we have the following snapshot of our queue, which represents the next level: [4, 5, 6].
- Update
ans
to the first node's value in the queue, which is now 4. - The current level has three nodes. We need to process each:
- Pop node 4 from the queue; as it has no children, we do not append anything to the queue. The queue becomes [5, 6].
- Pop node 5, and since it has a left child (node 7), we append node 7 to the queue. We don't append anything for the right child as it doesn't exist. The queue is now [6, 7].
- Pop node 6 from the queue; as it has no children, we do not append anything to the queue. The queue becomes [7].
- Update
-
One final iteration shows us that we are at the last level. Update
ans
to 7, and process the only node at this level:- Pop node 7 from the queue; it has no children, so the queue is now empty.
-
The queue is empty, and the while loop exits. The
ans
value, which is 7, is our final result. It represents the leftmost value of the last row in the binary tree. -
We return the value stored in
ans
, which is 7, as the leftmost value in the tree's last row.
Solution Implementation
1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5 def __init__(self, val=0, left=None, right=None):
6 self.val = val
7 self.left = left
8 self.right = right
9
10class Solution:
11 def findBottomLeftValue(self, root: TreeNode) -> int:
12 # Initialize a queue with the root node.
13 node_queue = deque([root])
14
15 # This will hold the leftmost value as the tree is traversed level by level.
16 bottom_left_value = 0
17
18 # Perform a level order traversal on the tree.
19 while node_queue:
20 # At new level's beginning, the first node is the leftmost node.
21 bottom_left_value = node_queue[0].val
22
23 # Iterate through nodes at the current level.
24 for _ in range(len(node_queue)):
25 # Pop the node from the front of the queue.
26 node = node_queue.popleft()
27
28 # If the left child exists, add it to the queue.
29 if node.left:
30 node_queue.append(node.left)
31 # If the right child exists, add it to the queue.
32 if node.right:
33 node_queue.append(node.right)
34
35 # Return the bottom left value found during traversal.
36 return bottom_left_value
37
1// Definition for a binary tree node.
2class TreeNode {
3 int val;
4 TreeNode left;
5 TreeNode right;
6
7 TreeNode() {}
8
9 // Constructor for creating a new node with a given value.
10 TreeNode(int val) {
11 this.val = val;
12 }
13
14 // Constructor for creating a new node with a given value and left & right children.
15 TreeNode(int val, TreeNode left, TreeNode right) {
16 this.val = val;
17 this.left = left;
18 this.right = right;
19 }
20}
21
22class Solution {
23 /**
24 * Finds the value of the bottom-leftmost node in a binary tree using level order traversal.
25 *
26 * @param root The root node of the binary tree.
27 * @return The value of the bottom-leftmost node.
28 */
29 public int findBottomLeftValue(TreeNode root) {
30 // Initialize a queue to hold tree nodes in level order.
31 Queue<TreeNode> queue = new ArrayDeque<>();
32
33 // Begin with the root node.
34 queue.offer(root);
35
36 // This will hold the most recent leftmost value found at each level.
37 int bottomLeftValue = 0;
38
39 // Traverse the tree level by level.
40 while (!queue.isEmpty()) {
41 // Update the bottomLeftValue with the value of the first node in this level.
42 bottomLeftValue = queue.peek().val;
43
44 // Process each node in the current level and enqueue their children.
45 for (int i = queue.size(); i > 0; --i) {
46 TreeNode node = queue.poll();
47
48 // Enqueue the left child if it exists.
49 if (node.left != null) {
50 queue.offer(node.left);
51 }
52
53 // Enqueue the right child if it exists.
54 if (node.right != null) {
55 queue.offer(node.right);
56 }
57 }
58 }
59
60 // Return the bottom-leftmost value found.
61 return bottomLeftValue;
62 }
63}
64
1// Definition for a binary tree node.
2struct TreeNode {
3 int val;
4 TreeNode *left;
5 TreeNode *right;
6 TreeNode() : val(0), left(nullptr), right(nullptr) {}
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
9};
10
11class Solution {
12public:
13 // Finds the leftmost bottom value in a binary tree.
14 int findBottomLeftValue(TreeNode* root) {
15 // Initialize a queue to perform level order traversal
16 std::queue<TreeNode*> queue{{root}};
17
18 // Variable to store the leftmost value as we traverse
19 int bottomLeftValue = 0;
20
21 // Loop until the queue is empty
22 while (!queue.empty()) {
23 // Get the value of the current front node as it could be the leftmost node of this level
24 bottomLeftValue = queue.front()->val;
25
26 // Iterate over all the nodes at the current level
27 for (int i = static_cast<int>(queue.size()); i > 0; --i) {
28 TreeNode* currentNode = queue.front();
29 queue.pop();
30
31 // If the left child exists, add it to the queue for the next level
32 if (currentNode->left) queue.push(currentNode->left);
33 // If the right child exists, add it to the queue for the next level
34 if (currentNode->right) queue.push(currentNode->right);
35 }
36 }
37
38 // After traversing the whole tree, bottomLeftValue will contain the leftmost value of the bottom level
39 return bottomLeftValue;
40 }
41};
42
1// Function to find the bottom-left value of a binary tree.
2function findBottomLeftValue(root: TreeNode | null): number {
3 let bottomLeftValue = 0; // Initialize a variable to store the bottom-left value.
4
5 // Initialize a queue for level-order traversal starting with the root node.
6 const queue: Array<TreeNode | null> = [root];
7
8 // Execute while there are nodes to process in the queue.
9 while (queue.length > 0) {
10 // The first node's value of each level is the potential bottom-left value.
11 bottomLeftValue = queue[0].val;
12
13 // Traverse the current level.
14 for (let i = queue.length; i > 0; --i) {
15 // Remove the node from the front of the queue.
16 const currentNode: TreeNode | null | undefined = queue.shift();
17
18 // If the current node has a left child, add it to the queue.
19 if (currentNode && currentNode.left) {
20 queue.push(currentNode.left);
21 }
22
23 // If the current node has a right child, add it to the queue.
24 if (currentNode && currentNode.right) {
25 queue.push(currentNode.right);
26 }
27 }
28 }
29
30 // After the traversal, bottomLeftValue will contain the leftmost value of the bottom-most level.
31 return bottomLeftValue;
32}
33
Time and Space Complexity
Time Complexity
The time complexity of the code is O(N)
, where N
is the number of nodes in the tree. This is because the code performs a breadth-first search (BFS) of the tree, visiting each node exactly once.
Space Complexity
The space complexity is also O(N)
. In the worst case, the queue could have all nodes at the last level of a complete binary tree. In a complete binary tree, the number of nodes at the last level is approximately N/2
. Since N/2
is still in the order of N
, the space complexity is O(N)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Want a Structured Path to Master System Design Too? Donāt Miss This!