Find Bottom Left Tree Value

Problem

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:
Input:

    2
   / \
  1   3

Output:
1

Example 2: 
Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution

BFS Solution: O(n) time, O(n) space

public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        TreeNode node = null;
        while (!q.isEmpty()) {
            node = q.poll();
            if (node.right != null) q.offer(node.right);
            if (node.left != null) q.offer(node.left);
        }
        return node.val;
    }
}

Recursive Solution: O(n) time, O(n) space

public class Solution {

    public int findBottomLeftValue(TreeNode root) {
        int[] res = new int[2];
        helper(res, root, 1);
        return res[1];
    }

    private void helper(int[] res, TreeNode node, int level) {
        if (node == null) return;
        if (res[0] < level) {
            res[0] = level;
            res[1] = node.val;
        }
        helper(res, node.left, level + 1);
        helper(res, node.right, level + 1);
    }
}

Analysis

We need to get the value of leftmost node in given tree
In the BFS solution, we first add the node.right and then add the node.left if it's not null
Because of FIFO property of queue, the last node from queue must be the leftmost node
This is because we make sure the tail of queue is always node.left
If node.left in the last level is null, node.right is the expected value we need to return

In the recursive solution, because we cannot pop() the nodes timely, we have to have help() method
In that method, we need to record the current level
We also have int[] res to record the returned value
As long as the current level reaches deeper, which means res[0] < level
We update res[0] = level and res[1] = node.val
And then we just recursively call helper() method with node.left and node.right with level + 1
Because we call node.left first, the res[] will be updated before node.right reaches