Three-part traversal
void leftBoundary(Node n, List result) {
if (n == null || (n.left == null && n.right == null)) return;
result.add(n.val);
if (n.left != null) leftBoundary(n.left, result);
else leftBoundary(n.right, result);
}
void leaves(Node n, List result) {
if (n == null) return;
if (n.left == null && n.right == null) { result.add(n.val); return; }
leaves(n.left, result); leaves(n.right, result);
}
void rightBoundary(Node n, List result) {
if (n == null || (n.left == null && n.right == null)) return;
if (n.right != null) rightBoundary(n.right, result);
else rightBoundary(n.left, result);
result.add(n.val); // add AFTER recursion for reverse order
} Advertisement
Edge cases
Root always included. If only one child, that path is both left + right boundary. Handle carefully.
Advertisement
Complexity
O(N) time. Each node visited once.