What happens if you visiting right child before left in dfs?

Incorrect leftmost node recorded at deepest level Fix: Always visit left child before right in DFS

What happens if you using dfs without tracking depth correctly?

May return wrong node or cause runtime errors Fix: Pass depth parameter correctly and update max_depth accordingly

What happens if you in bfs, not resetting leftmost value at each level?

Leftmost value may be from wrong level Fix: Update leftmost value at the start of each level processing

Interview Preptree-bfsmediumAmazonGoogle

Find Bottom Left Tree Value

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumTREEAmazonGoogle

Imagine you are looking at a tree from the bottom left side and want to find the value of the node that would be visible there.

💡 This problem requires understanding how to traverse a tree level by level and identify the leftmost node at the last level. Beginners often struggle because they focus on depth-first traversal or confuse leftmost with rightmost nodes.

📋

Problem Statement

Given the root of a binary tree, return the value of the leftmost node in the last row of the tree.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be positive, negative, or zero.

💡

Example

Input"root = [2,1,3]"

Output1

The last row has nodes 1 and 3, the leftmost is 1.

Input"root = [1,2,3,4,null,5,6,null,null,7]"

Output7

The last row has node 7 as the leftmost node.

Single node tree → output is the root value
Tree with only left children → output is the bottom-most left child
Tree with only right children → output is the bottom-most right child (which is also leftmost at that level)
Complete binary tree → output is the leftmost node at the last level

⚠️

Common Mistakes

Visiting right child before left in DFS

Incorrect leftmost node recorded at deepest level

✅ Always visit left child before right in DFS

Updating leftmost value for every node at max depth instead of only first

Overwrites leftmost value with right nodes at same depth

✅ Update leftmost value only when depth > max_depth, not equal

Using DFS without tracking depth correctly

May return wrong node or cause runtime errors

✅ Pass depth parameter correctly and update max_depth accordingly

In BFS, not resetting leftmost value at each level

Leftmost value may be from wrong level

✅ Update leftmost value at the start of each level processing

In BFS optimal approach, adding left child before right child

Last node popped is not bottom left node

✅ Add right child before left child to queue

🧠

Brute Force (DFS with Tracking Depth and Leftmost Node)

💡 This approach uses a simple depth-first search to explore all nodes, tracking the deepest level and the leftmost node found at that level. It is intuitive and helps understand the problem deeply before optimizing.

Intuition

Traverse the tree recursively, keeping track of the current depth. Whenever you reach a new maximum depth, record the node's value as the leftmost node at that depth.

Algorithm

Initialize variables to track maximum depth and leftmost value.
Perform DFS starting from root at depth 0.
At each node, if current depth > max depth, update max depth and leftmost value.
Recursively visit left child first, then right child to ensure leftmost priority.

💡 The key is visiting left child before right to ensure the first node at a new depth is the leftmost.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_depth = -1
        self.leftmost_value = 0

        def dfs(node, depth):
            if not node:
                return
            if depth > self.max_depth:
                self.max_depth = depth
                self.leftmost_value = node.val
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return self.leftmost_value

# Driver code to test
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5, TreeNode(7)), TreeNode(6)))
    sol = Solution()
    print(sol.findBottomLeftValue(root))  # Expected output: 7

Line Notes

self.max_depth = -1Initialize max_depth to -1 to ensure root at depth 0 updates it

self.leftmost_value = 0Placeholder for leftmost value, updated when deeper node found

if depth > self.max_depth:Check if current node is deeper than any previously visited

dfs(node.left, depth + 1)Visit left child first to prioritize leftmost nodes

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private int maxDepth = -1;
    private int leftmostValue = 0;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return leftmostValue;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) return;
        if (depth > maxDepth) {
            maxDepth = depth;
            leftmostValue = node.val;
        }
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }

    // Driver code
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.right.left.left = new TreeNode(7);

        Solution sol = new Solution();
        System.out.println(sol.findBottomLeftValue(root)); // Expected: 7
    }
}

Line Notes

private int maxDepth = -1;Initialize maxDepth to -1 so root at depth 0 updates it

if (depth > maxDepth)Update leftmostValue only when a deeper node is found

dfs(node.left, depth + 1);Traverse left subtree first to ensure leftmost priority

public static void main(String[] args)Driver code to test the solution with example tree

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    int maxDepth = -1;
    int leftmostValue = 0;

    void dfs(TreeNode* node, int depth) {
        if (!node) return;
        if (depth > maxDepth) {
            maxDepth = depth;
            leftmostValue = node->val;
        }
        dfs(node->left, depth + 1);
        dfs(node->right, depth + 1);
    }

public:
    int findBottomLeftValue(TreeNode* root) {
        dfs(root, 0);
        return leftmostValue;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->right->left->left = new TreeNode(7);

    Solution sol;
    cout << sol.findBottomLeftValue(root) << endl; // Expected: 7
    return 0;
}

Line Notes

int maxDepth = -1;Start maxDepth at -1 so root at depth 0 updates it

if (depth > maxDepth)Update leftmostValue only when a deeper node is found

dfs(node->left, depth + 1);Visit left child first to prioritize leftmost nodes

int main()Driver code to build example tree and test solution

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    constructor() {
        this.maxDepth = -1;
        this.leftmostValue = 0;
    }

    findBottomLeftValue(root) {
        const dfs = (node, depth) => {
            if (!node) return;
            if (depth > this.maxDepth) {
                this.maxDepth = depth;
                this.leftmostValue = node.val;
            }
            dfs(node.left, depth + 1);
            dfs(node.right, depth + 1);
        };
        dfs(root, 0);
        return this.leftmostValue;
    }
}

// Driver code
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4)),
    new TreeNode(3, new TreeNode(5, new TreeNode(7)), new TreeNode(6))
);
const sol = new Solution();
console.log(sol.findBottomLeftValue(root)); // Expected output: 7

Line Notes

this.maxDepth = -1;Initialize maxDepth so root at depth 0 updates it

if (depth > this.maxDepth)Update leftmostValue only when a deeper node is found

dfs(node.left, depth + 1);Traverse left subtree first to ensure leftmost priority

console.log(sol.findBottomLeftValue(root));Print result to verify correctness

⏱

Complexity

TimeO(n)

SpaceO(h)

We visit each node once (n nodes). The recursion stack can go as deep as the tree height h.

💡 For a tree with 100,000 nodes, this means 100,000 visits; stack depth depends on tree shape.

Interview Verdict: Accepted

This approach is efficient enough for large trees and easy to implement, making it a solid baseline.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with depth tracking)	`O(n)`	`O(h) recursion stack`	Yes (deep trees)	N/A	Good to explain problem understanding; code if comfortable with recursion
2. Better (BFS level order traversal)	`O(n)`	`O(w) queue size`	No	N/A	Preferred approach to code in interviews for clarity and safety
3. Optimal (BFS with right-to-left insertion)	`O(n)`	`O(w) queue size`	No	N/A	Good to mention as optimization; code if confident

Practice

(1/5)

1. You are given a binary tree and asked to compute the average value of nodes on each level. Which algorithmic approach guarantees an optimal solution that processes nodes level-by-level and efficiently computes these averages?

easy

A. Depth-first search (DFS) without tracking levels, summing all nodes and dividing by total count.

B. Breadth-first search (BFS) using a queue to traverse nodes level-by-level, summing values per level and dividing by the number of nodes at that level.

C. Greedy approach that picks the maximum node value at each level and averages those maximums.

D. Dynamic programming that stores partial sums of subtrees and combines them bottom-up.

3. The following code attempts the optimal DFS approach for bottom-up level order traversal. Identify the line containing the subtle bug that causes incorrect output for an empty tree input.

def levelOrderBottom(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return levels[::-1]

medium

A. Line 10: dfs(root, 0)

B. Line 11: return levels[::-1]

C. Line 2: levels = []

D. Line 3: def dfs(node, level):

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand the problem requires level-wise aggregation

Step 2: Identify BFS as the natural approach for level order traversal

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem requires level-wise traversal

Step 2: Identify BFS as the natural approach for level order traversal

Final Answer:

Quick Check:

Solution

Step 1: Consider empty tree input (root = None)

Step 2: Check what happens after dfs call

Step 3: Identify bug

Final Answer:

Quick Check:

Solution

Step 1: Identify how children are enqueued

Step 2: Understand consequence of bug

Final Answer:

Quick Check:

Solution

Step 1: Understand problem extension

Step 2: Evaluate modifications

Final Answer:

Quick Check:

Ready to prove it?