How to find bottom left value in a binary tree

Given a binary tree, return the left bottom value

Example 1

Input:         1   
              / \  
        -->  5   3 

Output: 5

Example 2

Input:       1   
              \  
        -->    3 

Output: 3

As usual, for a better understanding of the problem, we're starting from the examples

 

 

The bottom left value of a binary tree is the deepest left leaf node in a binary tree. Imagine you're looking on a binary tree from the left side and the deepest left leaf will be the bottom left value.

 

 

for our examples, it will be: 2, 3 and 4

 

 

To find out the bottom left value we can recursively traverse the binary tree, during traversing maintain level and node value. We are searching for the left value, so we need to visit the left subtree first.

 

 

L1, L2, L3 - levels: level 1, level 2 and level 3

Algorithm

• recursively traverse the binary tree
  • maintain level and node value
  • visit left subtree first
• if the new level greater than the stored level
  • update the stored level and the node value

Code

    public int BottomLeftValue(TreeNode root)
    {
        if (root == null)
        {
            return -1;
        }
        // the level is 0 and value equals root value
        int[] result = { 0, root.Value };
        BottomLeftValue(root, 0, result);
        return result[1];
    }

    private void BottomLeftValue(TreeNode root, int level, int[] result)
    {
        if (root == null)
        {
            return;
        }

        if (level > result[0])
        {
            result[0] = level;
            result[1] = root.Value;
        }

        BottomLeftValue(root.Left, level + 1, result);
        BottomLeftValue(root.Right, level + 1, result);
    }

Time Complexity: O(n)