LeetCode 513 - Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value/

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.

https://discuss.leetcode.com/topic/78962/simple-java-solution-beats-100-0

    int ans=0, h=0;
    public int findLeftMostNode(TreeNode root) {
        findLeftMostNode(root, 1);
        return ans;
    }
    public void findLeftMostNode(TreeNode root, int depth) {
        if (h<depth) {ans=root.val;h=depth;}
        if (root.left!=null) findLeftMostNode(root.left, depth+1);
        if (root.right!=null) findLeftMostNode(root.right, depth+1);
    }

    public int findBottomLeftValue(TreeNode root) {
        return findBottomLeftValue(root, 1, new int[]{0,0});
    }
    public int findBottomLeftValue(TreeNode root, int depth, int[] res) {
        if (res[1]<depth) {res[0]=root.val;res[1]=depth;}
        if (root.left!=null) findBottomLeftValue(root.left, depth+1, res);
        if (root.right!=null) findBottomLeftValue(root.right, depth+1, res);
        return res[0];
    }

X. Level Order traversal
https://discuss.leetcode.com/topic/78954/verbose-java-solution-binary-tree-level-order-traversal
https://discuss.leetcode.com/topic/78941/java-bfs

Typical way to do binary tree level order traversal. Only additional step is to remember the first element of each level.

    public int findLeftMostNode(TreeNode root) {
        if (root == null) return 0;
        
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0) result = node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        
        return result;
    }

https://discuss.leetcode.com/topic/78981/right-to-left-bfs-python-java
Doing BFS right to left means we can simply return the last node's value and don't have to keep track of the first node in the current tree row.

public int findLeftMostNode(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.right != null)
            queue.add(root.right);
        if (root.left != null)
            queue.add(root.left);
    }
    return root.val;
}

X. https://leetcode.com/problems/find-bottom-left-tree-value/discuss/98822/Java-solution-by-post-order-traversal-(beats-54)

Since most of the answers use pre-order and level-order traversal. Here is my post-order traversal solution as an inspiration. The idea is to get the bottom left value of each subtree at each root, compare their depths and pass onto its parent.

private class ResultSet {
    final int depth;
    final int val;

    ResultSet(int depth, int val) {
        this.depth = depth;
        this.val = val;
    }
}

public int findBottomLeftValue(TreeNode root) {
    return bottomLeft(root, 0).val;
}

private ResultSet bottomLeft(TreeNode root, int depth) {
    if (root == null) return null;
    if (root.left == null && root.right == null) return new ResultSet(depth, root.val);
    else if (root.left == null) return bottomLeft(root.right, depth + 1);
    else if (root.right == null) return bottomLeft(root.left, depth + 1);
    else {
        ResultSet left = bottomLeft(root.left, depth + 1);
        ResultSet right = bottomLeft(root.right, depth + 1);
        return right.depth > left.depth ? right : left;
    }
}