# 513. Find Bottom Left Tree Value

## Approach 1: BFS

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: int findBottomLeftValue(TreeNode* root) { queue 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int findBottomLeftValue(TreeNode root) { Queue 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: q = collections.deque([root]) while q: root = q.popleft() if root.right: q.append(root.right) if root.left: q.append(root.left) return root.val 

## Approach 2: DFS

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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 == nullptr) 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); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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