# Leetcode: Find-bottom-left-tree-value

https://leetcode.com/problems/find-bottom-left-tree-value/

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

Example 1: Input:

  2
/ \
1   3


Output: 1 Example 2: Input:

    1
/ \
2   3
/   / \
4   5   6
/
7


Output: 7 Note: You may assume the tree (i.e., the given root node) is not NULL.

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace GraphsQuestions
{
/// <summary>
/// https://leetcode.com/problems/find-bottom-left-tree-value/
/// </summary>
[TestClass]
public class FindBottomLeftTreeValue
{
//Input:

//   2
//  / \
// 1   3
[TestMethod]
public void SmallTreeTest()
{
TreeNode root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);
Assert.AreEqual(1, FindBottomLeftValue(root));
}

//Input:

//         1
//        / \
//       2   3
//      /   / \
//     4   5   6
//        /
//       7
[TestMethod]
public void BigTreeTest()
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(4);

root.right = new TreeNode(3);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);
root.right.left.left = new TreeNode(7);
Assert.AreEqual(7, FindBottomLeftValue(root));
}

public int FindBottomLeftValue(TreeNode root)
{
if (root == null)
{
throw new NullReferenceException("root is empty");
}
Queue<TreeNode> Q = new Queue<TreeNode>();
Q.Enqueue(root);
int left = root.val;
while (Q.Count > 0)
{
// we always push the left node first then we peek, so the first item is the most left
//for the entire level of the tree
int qSize = Q.Count;
left = Q.Peek().val;
for (int i = 0; i < qSize; i++)
{
var current = Q.Dequeue();
if (current.left != null)
{
Q.Enqueue(current.left);
}

if (current.right != null)
{
Q.Enqueue(current.right);
}
}
}

return left;
}
}

/*
Definition for a binary tree node.*/
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
}


• It's clear that all nodes must be visited to compute the correct answer, so the solution cannot be better than $$\O(n)\$$ time.
Without knowing in advance the shape of the tree (whether it's deep or wide), and given TreeNode as defined and no additional helper data structures, it's not possible to tell whether DFS or BFS is better. So they are both equally fine, as neither uses space excessively.