513. Find Bottom Left Tree Value.md

513. Find Bottom Left Tree Value | C++ Solution | Breadth-First Search (BFS) | Depth-First Search (DFS) | Optimized Approach

Intuition

The problem is asking to find the leftmost value in the last row of a binary tree. This means we need to traverse the tree to the deepest level and then return the leftmost node at that level.

Approach

1. Depth-First Search (DFS): We can use DFS to find the height of the tree and then traverse the tree again to find the leftmost node at the deepest level. We traverse the right subtree before the left subtree because we want to overwrite the value of the leftmost node if there is a deeper level in the left subtree.

2. Breadth-First Search (BFS): We can use BFS to traverse the tree level by level from left to right. The last node we visit will be the leftmost node at the deepest level because we visit the leftmost node at each level before visiting the other nodes at the same level.

Complexity

• Depth-First Search (DFS):

  • Time complexity: $O(n)$ because we traverse each node twice, once to find the height of the tree and once to find the leftmost node at the deepest level.
  • Space complexity: $O(n)$ in the worst case when the tree is completely unbalanced, e.g., each node has only left child node, and $O(\log n)$ in the best case when the tree is completely balanced.

• Breadth-First Search (BFS):

  • Time complexity: $O(n)$ because we traverse each node once.
  • Space complexity: $O(w)$ where $w$ is the maximum width of the tree, which is the maximum number of nodes at any level in the tree.

Code

1. Depth-First Search (DFS)

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL)
            return 0;
        return 1 + max(height(root->left), height(root->right));
    }

    void help(TreeNode* root, int h, int& ans) {
        if (root == NULL)
            return;
        if (h == 0) {
            ans = root->val;
            return;
        }
        help(root->right, h - 1, ans);
        help(root->left, h - 1, ans);
    }

    int findBottomLeftValue(TreeNode* root) {
        if (root == NULL)
            return 0;
        int h = 0;
        h = height(root) - 1;

        int ans = 0;

        if (h == 0) {
            while (root->right != NULL) {
                root = root->right;
            }
            return root->val;
        }

        help(root, h, ans);

        return ans;
    }
};

2. Breadth-First Search (BFS)

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            root = q.front();
            q.pop();
            if (root->right != NULL) {
                q.push(root->right);
            }
            if (root->left != NULL) {
                q.push(root->left);
            }
        }
        return root->val;
    }
};