# Verbose Java Solution, Binary tree level order traversal

• Typical way to do binary tree level order traversal. Only additional step is to remember the `first` element of each level.

``````public class Solution {
public int findLeftMostNode(TreeNode root) {
if (root == null) return 0;

int result = 0;

while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == 0) result = node.val;
}
}

return result;
}
}
``````

• @shawngao
Does it work for the tree below? Correct answer is B.

``````A
``````

/
B C

D

I believe it needs a postorder traversal.

• @shawngao
Does it work for the tree below? Correct answer is B.

``````A
``````

/
B C

D

I believe it needs a postorder traversal.

After posted, it messed up the tree. A is root, has two child B & C, C has a right child D.

• Typical way to do binary tree level order traversal. Only additional step is to remember the `first` element of each level.

``````public class Solution {
public int findLeftMostNode(TreeNode root) {
if (root == null) return 0;

int result = 0;

while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == 0) result = node.val;
}
}

return result;
}
}
``````

Checked the result with leetcode. your solution is right. It doesn't have to be the left leave. your solution is really neat.

• level order，but first add right child，then add left child。and change the value of result

``````public int findBottomLeftValue(TreeNode root) {

int result=0;
queue.offer(root);
while(!queue.isEmpty()){

TreeNode node=queue.poll();
result=node.val;
if(node.right!=null)
queue.offer(node.right);
if(node.left!=null)
queue.offer(node.left);
}

return result;

}
``````

• Minor Change
you could remove the `if(i == 0)` check, and do
`result = queue.peek().val` before the for loop. It would save a lot of if checks

• @szk258 yup, that makes sense.

• Python version:

``````class Solution(object):
def findBottomLeftValue(self, root):
q = collections.deque()
res = None
q.appendleft(root)

while q:
sz = len(q)
for i in xrange(0, sz):
node = q.popleft()
if i == 0:
res = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
``````

Javascript version:

``````var findBottomLeftValue = function(root) {
var result = 0;
var queue = []
queue.push(root);

while(queue.length > 0) {
var size = queue.length;
for(var i = 0; i < size; i++) {
var node = queue.shift()
if(i == 0) result = node.val;
if(node.left != null) queue.push(node.left);
if(node.right != null) queue.push(node.right);
}
}
return result;
};
``````

C++ version:

``````class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int result = 0;
queue<TreeNode*> queuee;
queuee.push(root);

while(queuee.size()) {
int size = queuee.size();
for(int i = 0; i < size; i++) {
TreeNode* node = queuee.front(); queuee.pop();
if(i == 0) result = node->val;
if(node->left != NULL) queuee.push(node->left);
if(node->right != NULL) queuee.push(node->right);
}
}
return result;
}
};
``````

Golang:

``````func findBottomLeftValue(root *TreeNode) int {
result := 0
q := make([]*TreeNode, 0)
q = append(q, root)

for len(q) > 0 {
sz := len(q)
for i:= 0; i < sz; i++ {
node := q[0]
q = q[1:]
if i == 0 {
result = node.Val
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
}
return result
}
``````

• @szk258 I tried this method and it brings me up to the 17ms (from 10), thx a lot.

• Same idea here, but seems to be faster.

``````public class Solution {
public int findBottomLeftValue(TreeNode root) {
TreeNode leftMost = root;
q.offer(root);
while (!q.isEmpty()) {
int qSize = q.size();
leftMost = q.peek();
while (qSize-- > 0) {
TreeNode curr = q.poll();
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
}
return leftMost.val;
}
}
``````

• DFS (86%)

``````public int findBottomLeftValue(TreeNode root) {
int[] levelVal = new int[] {-1, -1};
if(root != null) findBottom(root, 0, levelVal);
return levelVal[1];
}
private void findBottom(TreeNode root, int level, int[] levelVal) {
if(level > levelVal[0] && root.left == null && root.right == null) {
levelVal[0] = level;
levelVal[1] = root.val;
}
if(root.left != null) findBottom(root.left, level+1, levelVal);
if(root.right != null) findBottom(root.right, level+1, levelVal);
}``````

• DFS solution :

class NodeAtDepth{
int val = 0;
int depth = 0;
}
public int findBottomLeftValue(TreeNode root) {
}

``````public void getBottomLeftValue(TreeNode node, int currentDepth,NodeAtDepth nad) {
if(node == null) return;
}
}``````

• Using a List to record first left node on each level, return the one for bottom level.

``````    public int findBottomLeftValue(TreeNode root) {
List<Integer> levelLeft = new ArrayList();
int maxLevel = helper(levelLeft, root, 0);
return levelLeft.get(maxLevel);
}

int helper(List<Integer> levelLeft, TreeNode root, int level){
if(root == null) return level - 1;