# Right-to-Left BFS (Python + Java)

• Doing BFS right-to-left means we can simply return the last node's value and don't have to keep track of the first node in the current row or even care about rows at all. Inspired by @fallcreek's solution (not published) which uses two nested loops to go row by row but already had the right-to-left idea making it easier. I just took that further.

Python:

``````def findLeftMostNode(self, root):
queue = [root]
for node in queue:
queue += filter(None, (node.right, node.left))
return node.val
``````

Java:

``````public int findLeftMostNode(TreeNode root) {
while (!queue.isEmpty()) {
root = queue.poll();
if (root.right != null)
if (root.left != null)
}
return root.val;
}``````

• dude you do know whole lotta tricks, you just simply switch the order of left and right while i spent time to write the naive level-order traversal, brilliant!

• @SB.Hu Well like I said, I got that idea from @fallcreek.

Edit: I just checked again, actually @fallcreek's solution does have nested loops, the inner loop going over one whole level. But the right-to-left idea was already there, and I just took full advantage of it.

• @StefanPochmann aha, didn't notice there are description on top, good job anyway.

• Dude thanks for inspiring. Just one quick question as for the "(node.right, node.left)" that I did not figure out by researching. Does that work like appending node.right first and then node.left to the queue? And is the type of "(node.right, node.left)" just a group of elements or a list-like.

Thanks very much!

• This post is deleted!

• @StefanPochmann I have a question: For below example, the code will return 4.
It is not left leaf, why it is correct?
1
/     \
2     3
\     /
4    5

• @yanchun said in Right-to-Left BFS (Python + Java):

It is not left leaf

Yes. And?

• @yanchun hi, this question asks for left most value of last level, it does not have to be a left left. Hope it helps.

• @StefanPochmann
Got it. I think I misunderstand the question. It is not left node value. Thank you.

• @jinping
Now I got it. I think I misunderstand the question. :) It is not left node value. Thank you.

• Whoa I didn't know the scope of a for loop variable stays with the last element.
Hence we didn't have to pop anything from queue, so don't have to use deque instead.

• Brilliant!!! It takes me few minutes to understand.

• Nice solution!

• This post is deleted!

• @Hellokitty_2015 What does that have to do with this thread / my solution?

• @StefanPochmann brilliant idea. A C++ version:

``````    int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
TreeNode* last;
while(!q.empty()){
last = q.front(), q.pop();
if(last->right) q.push(last->right);
if(last->left) q.push(last->left);
}
return last->val;
}
``````

• @SB.Hu Same here...!!!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.