513. Find Bottom Left Tree Value

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

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:

  1. Initialize a queue (in this case, q) with the root node of the binary tree. This queue will hold the nodes to be processed.

  2. Initialize a variable (ans) to keep track of the leftmost value.

  3. 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.

  4. 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.

  5. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example 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        1
2       / \
3      2   3
4     /   / \
5    4   5   6
6       /
7      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:

  1. Initialize the queue with the root node (which is 1 in this case). Our queue (q) looks like this: [1]

  2. Initialize the ans variable to keep track of the leftmost value. Currently, ans is not set.

  3. 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].

  4. 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].

  5. 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].

  6. 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.

  7. 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.

  8. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Everything About Trees

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

DFS Fundamentals

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

BFS Fundamentals

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ