intuitive Java DFS and BFS solution

  • 0

    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)
            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) {
            Queue<TreeNode> q = new LinkedList<>();
            int firstNodeVal = 0;
            boolean flag = true;
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                if (node == null) { // end of this level
                    if (q.isEmpty())
                    flag = true;    // indicate next node is the first node of this level
                else {
                    if (flag) {
                        firstNodeVal = node.val;
                        flag = false;
                    if (node.left != null)
                    if (node.right != null)
            return firstNodeVal;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.