Find Leaf Nodes (Tree)
Problem link: https://www.geeksforgeeks.org/print-leaf-nodes-binary-tree-right-left/
Problem Statement
Given the root of a binary tree, return (or print) all leaf nodes.
Input
root: binary tree root
Output
- List of leaf values (any order depending on traversal)
Example
1
/ \
2 3
/
4
output = [4, 3]
Explanation
Nodes 4 and 3 have no children.
Brute Force
Intuition
Traverse all nodes; whenever you see a node with no children, it’s a leaf.
Approach
Level-order (BFS): visit all nodes and collect leaves.
Code (Java)
Time: O(N)Space: O(N)
Complexity Analysis
- Time
O(N): each node is visited once. - Space
O(N): worst-case queue size can beO(N)for a wide tree.
Optimal Solution
Intuition
A leaf is any node with left == null and right == null.
DFS naturally reaches leaves and can collect them with only recursion stack space.
Approach
DFS is simpler and uses stack space proportional to tree height.
Code (Java)
import java.util.ArrayList;
import java.util.List;
public class FindLeafNodesDFS {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public static List<Integer> leafNodes(TreeNode root) {
List<Integer> leaves = new ArrayList<>();
dfs(root, leaves);
return leaves;
}
private static void dfs(TreeNode node, List<Integer> leaves) {
if (node == null) return;
if (node.left == null && node.right == null) {
leaves.add(node.val);
return;
}
dfs(node.left, leaves);
dfs(node.right, leaves);
}
}
Time: O(N)Space: O(H)
Complexity Analysis
- Time
O(N): each node is visited once. - Space
O(H): recursion stack depth is tree heightH(worst-caseNfor a skewed tree).
Quick Revision (Brute Force)
- BFS/level-order: visit all nodes and collect those with no children.
- Queue can grow large for wide trees.
- Time O(N), Space O(N).
Quick Revision (Optimal)
- DFS: when node has no children, add it to answer.
- Uses recursion stack proportional to height.
- Time O(N), Space O(H).