[LeetCode] Find Bottom Left Tree Value

Problem: Given the root of a binary tree, return the leftmost value in the last row of the tree.

Example:

Input: root = [2,1,3]
Output: 1

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7

Approach: We can use Level Order Traversal here. Basically while doing level order traversal, we can store the first element of the current level in a variable which is basically the left most element of that particular level in the tree.

In that way when the traversal ends, we will have the left most element of the last level.

Implementation in C#:

    public int FindBottomLeftValue(TreeNode root) 

    {

        if (root == null)

        {

            return -1;

        }

        Queue<TreeNode> queue = new Queue<TreeNode>();

        queue.Enqueue(root);

        int leftMostValue = -1;

        while(queue.Count > 0)

        {

            int queueSize = queue.Count;

            for (int i = 0; i < queueSize; ++i)

            {

                TreeNode node = queue.Dequeue();

                if (i == 0)

                {

                    leftMostValue = node.val;

                }

                if (node.left != null)

                {

                    queue.Enqueue(node.left);

                }    

                if (node.right != null)

                {

                    queue.Enqueue(node.right);

                }

            }

        }

        return leftMostValue;

    }

Complexity: O(n)