algoadvance

Leetcode 513. Find Bottom Left Tree Value

Problem Statement

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

Clarifying Questions

  1. Q: What is the maximum number of nodes in the binary tree? A: The binary tree can have at most 10⁴ nodes.

  2. Q: Can the binary tree contain duplicate values? A: Yes, the binary tree can contain duplicate values.

  3. Q: What should be returned if the tree is empty? A: Since the problem states that there is always a valid tree, the input tree will not be empty.

Strategy

  1. Level Order Traversal: We can use Breadth-First Search (BFS) to perform a level-order traversal of the tree. Using a queue, we can keep track of nodes level by level.
  2. Track the First Element of the Last Level: While performing the BFS, we can keep updating the value of the first node encountered in each level until the queue is empty. This way, the last updated value will be the leftmost value of the last row of the tree.

Code

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) {
            throw new IllegalArgumentException("The tree should have at least one node.");
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int leftmostValue = root.val;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();

                if (i == 0) {
                    leftmostValue = currentNode.val;
                }

                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
        }

        return leftmostValue;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(3);
        System.out.println(sol.findBottomLeftValue(root1)); // Output: 1

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.right.left = new TreeNode(5);
        root2.right.right = new TreeNode(6);
        root2.right.left.left = new TreeNode(7);
        System.out.println(sol.findBottomLeftValue(root2)); // Output: 7
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI