513. Find Bottom Left Tree Value - Explanation

# 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:
        q = deque([root])

        while q:
            node = q.popleft()
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)

        return node.val

# 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:
        self.maxDepth, self.res = -1, root.val

        def dfs(node, depth):
            if not node:
                return
            if depth > self.maxDepth:
                self.maxDepth, self.res = depth, node.val

            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return self.res

# 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 = root.val, -1
        stack = [(root, 0)]

        while stack:
            node, depth = stack.pop()
            if depth > maxDepth:
                maxDepth = depth
                res = node.val

            if node.right:
                stack.append((node.right, depth + 1))
            if node.left:
                stack.append((node.left, depth + 1))

        return res

# 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