Leetcode 513. Find Bottom Left Tree Value

Find Bottom Left Tree Value

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

DFS Recursive Approach 1


    /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode() {}
    *     TreeNode(int val) { this.val = val; }
    *     TreeNode(int val, TreeNode left, TreeNode right) {
    *         this.val = val;
    *         this.left = left;
    *         this.right = right;
    *     }
    * }
    */
   
   
    class Solution {
        int maxdepth;
        int bottoLeftMostValue;
        
        public int findBottomLeftValue(TreeNode root) {
            if(root == null)
                return 0;
            maxdepth = -1;
            bottoLeftMostValue = 0;
            dfs(root, 0); // traverse from root node with level 0
            return bottoLeftMostValue;
        }
        
        void dfs(TreeNode curr, int depth){
    
            if(curr == null) return;
            if(depth > maxdepth){
                maxdepth = depth;
                bottoLeftMostValue = curr.val;
            }
            dfs(curr.left, depth + 1); 
            dfs(curr.right, depth + 1); 
        }
    }

BFS Iterative Approach 2


class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue queue = new LinkedList<>();
        TreeNode current = root;
        queue.add(current);

        while (!queue.isEmpty()) {
            current = queue.poll();
            if (current.right != null) {
                queue.add(current.right);
            }
            if (current.left != null) {
                queue.add(current.left);
            }
        }
        return current.val;
    }
}

Introduction

Binary trees are fundamental in computer science, forming the basis for various algorithms and systems. One interesting problem in binary trees is finding the "bottom-left value," which refers to the leftmost value in the last row of the tree. This problem demonstrates traversal techniques like depth-first and breadth-first search, offering insights into tree operations.

Problem Statement

Given the root of a binary tree, find the value of the leftmost node in the bottom-most row. If the tree has only one level, the result is the root node's value. For deeper trees, the leftmost value of the deepest level is required.

This problem combines traversal techniques and understanding tree structure, making it an ideal test of algorithmic knowledge.

Approaches to Solve

There are two primary methods for finding the bottom-left tree value:

Depth-First Search (DFS): Explore each branch as deeply as possible before backtracking.
Breadth-First Search (BFS): Traverse level by level, processing all nodes at one depth before moving to the next.

Depth-First Search (DFS)

The DFS approach relies on a recursive strategy to explore the tree. While traversing, we track the depth and the leftmost value found at each level. The deepest level’s leftmost value is updated as the traversal progresses.

Algorithm:

function findBottomLeftValueDFS(node):
    maxDepth = -1
    bottomLeftValue = None

    function dfs(node, depth):
        if node is null:
            return
        if depth > maxDepth:
            maxDepth = depth
            bottomLeftValue = node.value
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(node, 0)
    return bottomLeftValue

This approach ensures that the leftmost value is updated only when a deeper level is reached, guaranteeing correctness.

Breadth-First Search (BFS)

The BFS approach uses a queue to traverse the tree level by level. The first node encountered at each level is considered the leftmost value for that level.

Algorithm:

function findBottomLeftValueBFS(root):
    queue = [root]
    while queue is not empty:
        node = queue.pop(0)
        if node.right is not null:
            queue.push(node.right)
        if node.left is not null:
            queue.push(node.left)
    return node.value

This method processes nodes from right to left at each level, ensuring the last processed node is the bottom-left value.

Examples

Consider the following binary tree:

               1
             /   \
            2     3
           / \   / \
          4   5 6   7
         /
        8

Using DFS:

Start at the root (1), with depth = 0.
Traverse left to node 2 (depth = 1), then to node 4 (depth = 2), and finally to node 8 (depth = 3).
Update the bottom-left value to 8 as it is the deepest and leftmost node.

Using BFS:

Traverse level by level: first 1, then 2 and 3, and so on.
The last node processed (8) is the bottom-left value.

Time and Space Complexity

Time Complexity:

Both DFS and BFS traverse all nodes once, resulting in O(n) time complexity, where n is the number of nodes.

Space Complexity:

DFS has O(h) space complexity, where h is the tree height (stack space).
BFS has O(w) space complexity, where w is the maximum width of the tree (queue space).

Applications

The problem of finding the bottom-left tree value has practical applications, including:

Tree-based decision-making systems, where the leftmost value at the deepest level represents the most prioritized decision.
Data retrieval in hierarchical structures, such as file systems.
Debugging or visualizing tree structures in software development.

Conclusion

Finding the bottom-left tree value is an essential problem that demonstrates the power of tree traversal techniques. Whether using DFS for depth-first exploration or BFS for breadth-first analysis, the problem emphasizes the importance of efficient traversal and algorithmic thinking. Mastering this concept is valuable for both theoretical understanding and practical applications.