Find Bottom Left Tree Value

Hi Geeks! Welcome to 100 Days of Leetcode Challenge. In this article, we going to see about how to find the bottom left tree value.

Day 44 of 100

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.

Solution

Before seeing the solution, think 3 to 5 minutes, how will you approach this problem? How can you come with the solution? If you really got some approach or solution, to solve this problem, please share it in comment section.

Best Approach to tackle this problem

We already know about level order traversal. If you don’t know, please check out my blog, I have written many articles related to level order traversal. I have solved 7 to 10 problems in trees using Level order traversal.

Perform Level Order Traversal with BFS approach.

BFS – Breadth First Search Approach. That is iterative way to find the level order traversal.

In this article, you can find the level order traversal with breadth first search approach. i.e by using Queue data structure.

Normally, we do BFS from left to right. But now, do BFS from right to left.

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. 

C# Program

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

        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        
        while(q.Count > 0)
        {
            root = q.Dequeue();
            if(root.right != null)
                q.Enqueue(root.right);
            if(root.left != null)
                q.Enqueue(root.left);
            
        }
        return root.val;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s