• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q{{root}};
TreeNode* node = nullptr;

while (!q.empty()) {
node = q.front();
q.pop();
if (node->right)
q.push(node->right);
if (node->left)
q.push(node->left);
}

return node->val;
}
};
``````

## JAVA

``````class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> q = new ArrayDeque<>(Arrays.asList(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;
}
}
``````

## Python

``````class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
q = deque([root])

while q:
root = q.popleft()
if root.right:
q.append(root.right)
if root.left:
q.append(root.left)

return root.val
``````

• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int ans = 0;
dfs(root, 1, 0, ans);
return ans;
}

private:
void dfs(TreeNode* root, int depth, int&& maxDepth, int& ans) {
if (!root)
return;
if (depth > maxDepth) {
maxDepth = depth;
ans = root->val;
}

dfs(root->left, depth + 1, move(maxDepth), ans);
dfs(root->right, depth + 1, move(maxDepth), ans);
}
};
``````

## JAVA

``````class Solution {
public int findBottomLeftValue(TreeNode root) {
dfs(root, 1);
return ans;
}

private int ans = 0;
private int maxDepth = 0;

private void dfs(TreeNode root, int depth) {
if (root == null)
return;
if (depth > maxDepth) {
maxDepth = depth;
ans = root.val;
}

dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
}
}
``````

## Python

``````class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
ans = 0
maxDepth = 0

def dfs(root: Optional[TreeNode], depth: int) -> None:
nonlocal ans
nonlocal maxDepth
if not root:
return
if depth > maxDepth:
maxDepth = depth
ans = root.val

dfs(root.left, depth + 1)
dfs(root.right, depth + 1)

dfs(root, 1)
return ans
``````