Find Bottom Left Tree Value - LeetCode Daily Challenge

Problem Statement

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

Example 1

Input: root = [2,1,3]
Output: 1

Example 2

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7

Try here before watching the video.

Video Solution

Java Code

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

C++ Code

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> queue;
        TreeNode* curr = root;
        queue.push(curr);
        while (!queue.empty()) {
            curr = queue.front();
            queue.pop();
            if (curr->right) {
                queue.push(curr->right);
            }
            if (curr->left) {
                queue.push(curr->left);
            }
        }
        return curr->val;
    }
};

Python Code

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:        
        queue = collections.deque()
        queue.append(root)
        
        while queue:
            curr = queue.popleft()
            if curr.right:
                queue.append(curr.right)
            if curr.left:
                queue.append(curr.left)
        
        return curr.val

Javascript Code

var findBottomLeftValue = function(root) {    
    let queue = [root];
    let curr;
    while (queue.length > 0) {
        curr = queue.shift();
        if (curr.right) queue.push(curr.right);
        if (curr.left) queue.push(curr.left);
    }
    return curr.val;
};

Go Code

func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    var curr *TreeNode 
    for len(queue) > 0 {
        curr = queue[0]
        queue = queue[1:]
        if curr.Right != nil {
            queue = append(queue, curr.Right)
        }
        if curr.Left != nil {
            queue = append(queue, curr.Left)
        }
    }
    return curr.Val
}

Complexity Analysis

Time Complexity: O(N), we are iterating over all the nodes.
Space Complexity: O(N), we are using a queue that would effectively store N elements.