Find Bottom Left Tree Value

• Initialize maxLevel = -1 and bottomLeftValue with a default value.
• Create a recursive helper function dfs(node, level).
• Start the traversal by calling dfs(root, 0).
• In dfs(node, level):
  • If node is null, return.
  • If the current level is greater than maxLevel, update maxLevel = level and bottomLeftValue = node.val.
  • Recursively call dfs(node.left, level + 1).
  • Recursively call dfs(node.right, level + 1).
• After the initial call completes, return bottomLeftValue.

The core idea is to traverse the tree while passing down the current level (or depth). We maintain two global or member variables: maxLevel to store the maximum depth reached, and bottomLeftValue to store the value of the leftmost node at that depth.\n\nWe define a helper function, dfs(node, level). The traversal order is crucial: we must visit the left subtree before the right one. This ensures that when we first encounter a new, deeper level, the node we are at is guaranteed to be the leftmost one for that level.\n\nInside the recursive function, we first check if the current level is greater than maxLevel. If it is, we've found a new deepest level. We update maxLevel to the current level and set bottomLeftValue to the current node's value. Then, we proceed with the recursive calls for the left and right children.\n\n```java /**

• Definition for a binary tree node.

• public class TreeNode {

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

• } */ class Solution { private int maxLevel = -1; private int bottomLeftValue = 0;

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

  private void dfs(TreeNode node, int level) { if (node == null) { return; }

  1// If this is the first time we visit this level, it must be the leftmost node.2if (level > maxLevel) {3    maxLevel = level;4    bottomLeftValue = node.val;5}6 7// Traverse left first to ensure we see the leftmost node first at any level.8dfs(node.left, level + 1);9dfs(node.right, level + 1);

  } }

• Initialize a queue and add the root node.
• Initialize a variable bottomLeftValue.
• Loop while the queue is not empty:
  • Determine the number of nodes on the current level, levelSize.
  • Loop levelSize times:
    • Dequeue a node.
    • If this is the first node of the level, update bottomLeftValue = node.val.
    • Enqueue the node's left child if it exists.
    • Enqueue the node's right child if it exists.
• After the loops complete, return bottomLeftValue.

We use a queue to implement BFS. We start by adding the root to the queue. The algorithm proceeds in a loop as long as the queue is not empty.\n\nIn each iteration of the main loop, we process an entire level. We first determine the number of nodes at the current level (levelSize). Then, we loop levelSize times, dequeuing one node at a time. The very first node we dequeue in this inner loop (i == 0) is the leftmost node of the current level. We store its value in our result variable. As we traverse deeper, this variable gets updated, and its final value will be from the last level.\n\nFor each dequeued node, we enqueue its left and right children, preparing them for the next level's processing.\n\n```java // Standard Left-to-Right BFS class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int bottomLeftValue = 0;

1    while (!queue.isEmpty()) {2        int levelSize = queue.size();3        for (int i = 0; i < levelSize; i++) {4            TreeNode currentNode = queue.poll();5            if (i == 0) {6                bottomLeftValue = currentNode.val;7            }8            if (currentNode.left != null) {9                queue.offer(currentNode.left);10            }11            if (currentNode.right != null) {12                queue.offer(currentNode.right);13            }14        }15    }16    return bottomLeftValue;17}

}

1A more elegant variation is to perform a right-to-left BFS. By enqueuing the right child before the left child, the last node we visit at any level is the leftmost one. This means the very last node processed in the entire traversal is our answer, simplifying the code.\n\n```java2// Right-to-Left BFS3class Solution {4    public int findBottomLeftValue(TreeNode root) {5        Queue<TreeNode> queue = new LinkedList<>();6        queue.offer(root);7        TreeNode currentNode = null;8 9        while (!queue.isEmpty()) {10            currentNode = queue.poll();11            if (currentNode.right != null) {12                queue.offer(currentNode.right);13            }14            if (currentNode.left != null) {15                queue.offer(currentNode.left);16            }17        }18        return currentNode.val;19    }20}