intuitive Java DFS and BFS solution

• DFS solution:
The main idea is using pre-order traversing of binary tree.

``````public class BottomLeftValue {
public static int findBottomLeftValue(TreeNode root) {
Tuple nominee = new Tuple(0, root.val);    // restore the max depth so far and corresponding left most value on this depth
int curDepth = 0;
dfs(root, nominee, curDepth);
return nominee.val;
}

public static class Tuple {
int depth;
int val;
public Tuple(int d, int value) {
depth = d;
val = value;
}

}

public static void dfs(TreeNode root, Tuple nominee, int curDepth) {
if (root == null)
return;
dfs(root.left, nominee, curDepth+1);
if (curDepth > nominee.depth) {
nominee.val = root.val;
nominee.depth = curDepth;
}
dfs(root.right, nominee, curDepth+1);

}
}
``````

BFS solution:
The key point is using `null` as the terminator of each level.

``````public static int bfsBottomLeftValue(TreeNode root) {
int firstNodeVal = 0;
boolean flag = true;
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) { // end of this level
if (q.isEmpty())
break;
flag = true;    // indicate next node is the first node of this level
}
else {
if (flag) {
firstNodeVal = node.val;
flag = false;
}
if (node.left != null)