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.