513. Find Bottom Left Tree Value

Tree Depth-First Search Breadth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

BFS level-order, processing right before left. The last node processed is the bottom-right. Or BFS left-before-right and take the last level's first element. Simplest: BFS right-to-left, return last node value.

Algorithm

1BFS with right child before left child.
2The last node dequeued is bottom-left.
3Return its value.

Common Pitfalls

•Using right-before-left BFS means the last element is leftmost. Alternatively, track first element of each level in standard BFS.

513.cs

// Approach: Reverse BFS — enqueue right child before left; the last dequeued
// node is the bottom-left (leftmost) node.
// Time: O(n) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public int FindBottomLeftValue(TreeNode root)
    {
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);

        while (q.Count > 0)
        {
            root = q.Dequeue();

            if (root.right != null)
                q.Enqueue(root.right);

            if (root.left != null)
                q.Enqueue(root.left);
        }

        return root.val;
    }
}

Was this solution helpful?