Find Bottom Left Tree Value

Medium · Graphs · Explanation and code example

Morris Traversal

How it works

Morris traversal lets us traverse the tree without using extra space for a stack or recursion. We temporarily modify the tree by threading right pointers of predecessor nodes back to their successors, creating a way to return after visiting the left subtree. We track depth manually by counting steps down and back up, updating our result whenever we reach a new maximum depth.

Steps

  1. Initialize res to the root's value, maxDepth to -1, curDepth to 0, and cur to root.
  2. While cur is not null:
    • If cur has no left child:
      • If curDepth > maxDepth, update maxDepth and res.
      • Move to the right child and increment curDepth.
    • Otherwise:
      • Find the rightmost node in the left subtree (the predecessor), counting steps.
      • If the predecessor's right pointer is null, set it to cur, move left, and increment curDepth.
      • If it points back to cur, restore it to null, decrement curDepth by the step count, and move right.
  3. Return res.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) extra space.

Things to watch for

Enqueueing Children in Wrong Order for BFS

The right-to-left BFS trick only works if right children are enqueued before left children. Reversing this order causes the last processed node to be the bottom-right instead of bottom-left.

Not Tracking Depth in DFS

When using DFS, updating the result without checking if the current depth exceeds the maximum seen depth causes incorrect values to be recorded. Always compare depths before updating the result.

Confusing Leftmost with First Encountered

The leftmost value at the deepest level is not necessarily the first node encountered during traversal. In DFS, left-first traversal combined with depth tracking ensures the leftmost node at maximum depth is correctly identified.

Python code example

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        res, maxDepth, curDepth = root.val, -1, 0
        cur = root

        while cur:
            if not cur.left:
                if curDepth > maxDepth:
                    maxDepth, res = curDepth, cur.val
                cur = cur.right
                curDepth += 1
            else:
                prev = cur.left
                steps = 1
                while prev.right and prev.right != cur:
                    prev = prev.right
                    steps += 1

                if not prev.right:
                    prev.right = cur
                    cur = cur.left
                    curDepth += 1
                else:
                    prev.right = None
                    curDepth -= steps
                    cur = cur.right

        return res

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int res = root->val, maxDepth = -1, curDepth = 0;
        TreeNode* cur = root;

        while (cur) {
            if (!cur->left) {
                if (curDepth > maxDepth) {
                    maxDepth = curDepth;
                    res = cur->val;
                }
                cur = cur->right;
                curDepth++;
            } else {
                TreeNode* prev = cur->left;
                int steps = 1;
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                    steps++;
                }

                if (!prev->right) {
                    prev->right = cur;
                    cur = cur->left;
                    curDepth++;
                } else {
                    prev->right = nullptr;
                    curDepth -= steps;
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations