Boundary of Binary Tree

medium tree dfs binary tree

Problem

Return the values on the boundary of a binary tree in anti-clockwise order.

Inputroot = [1,null,2,3,4]

Output[1,3,4,2]

Three DFS passes: left non-leaves, leaves, right non-leaves reversed.

tree (level-order, null allowed)

def boundary_of_binary_tree(root):
    if not root: return []
    res = [root.val] if (root.left or root.right) else [root.val]
    def lefts(n):
        if not n or (not n.left and not n.right): return
        res.append(n.val); lefts(n.left or n.right)
    def leaves(n):
        if not n: return
        if not n.left and not n.right: res.append(n.val); return
        leaves(n.left); leaves(n.right)
    def rights(n):
        if not n or (not n.left and not n.right): return
        rights(n.right or n.left); res.append(n.val)
    if root.left or root.right:
        lefts(root.left); leaves(root); rights(root.right)
    return res

function boundaryOfBinaryTree(root) {
  if (!root) return [];
  const res = [root.val];
  function lefts(n) { if (!n || (!n.left && !n.right)) return; res.push(n.val); lefts(n.left || n.right); }
  function leaves(n) { if (!n) return; if (!n.left && !n.right) { if (n !== root) res.push(n.val); return; } leaves(n.left); leaves(n.right); }
  function rights(n) { if (!n || (!n.left && !n.right)) return; rights(n.right || n.left); res.push(n.val); }
  if (root.left || root.right) {
    lefts(root.left);
    leaves(root);
    rights(root.right);
  }
  return res;
}

class Solution {
    List res = new ArrayList<>();
    TreeNode root;
    public List boundaryOfBinaryTree(TreeNode r) {
        if (r == null) return res;
        root = r;
        res.add(r.val);
        if (r.left != null || r.right != null) { lefts(r.left); leaves(r); rights(r.right); }
        return res;
    }
    void lefts(TreeNode n) { if (n == null || (n.left == null && n.right == null)) return; res.add(n.val); lefts(n.left != null ? n.left : n.right); }
    void leaves(TreeNode n) { if (n == null) return; if (n.left == null && n.right == null) { if (n != root) res.add(n.val); return; } leaves(n.left); leaves(n.right); }
    void rights(TreeNode n) { if (n == null || (n.left == null && n.right == null)) return; rights(n.right != null ? n.right : n.left); res.add(n.val); }
}

vector res; TreeNode* root;
void lefts(TreeNode* n) { if (!n || (!n->left && !n->right)) return; res.push_back(n->val); lefts(n->left ? n->left : n->right); }
void leaves(TreeNode* n) { if (!n) return; if (!n->left && !n->right) { if (n != root) res.push_back(n->val); return; } leaves(n->left); leaves(n->right); }
void rights(TreeNode* n) { if (!n || (!n->left && !n->right)) return; rights(n->right ? n->right : n->left); res.push_back(n->val); }
vector boundaryOfBinaryTree(TreeNode* r) {
    res.clear(); root = r; if (!r) return res;
    res.push_back(r->val);
    if (r->left || r->right) { lefts(r->left); leaves(r); rights(r->right); }
    return res;
}

Explanation

The boundary is the outline you would trace going anti-clockwise around the tree. The clean way is to split it into three pieces that are easy to collect separately: the left edge, the bottom (leaves), and the right edge in reverse.

We start by adding the root. Then lefts walks down the left side adding each non-leaf node top-down, always preferring the left child but falling back to the right when there is no left. This traces the leftmost spine.

Next, leaves does a normal DFS and adds every leaf in left-to-right order. Finally rights walks the right side but pushes values after recursing, so the right spine comes out bottom-up (reversed), completing the anti-clockwise loop.

Skipping leaves in the left and right passes avoids counting any node twice, since leaves are handled by the middle pass. Example: tree [1, null, 2, 3, 4] gives root 1, no left non-leaves, leaves 3 and 4, then right non-leaf 2 → [1, 3, 4, 2].

Each pass touches nodes at most once, so the total is O(n) time.

Time: O(n) Space: O(h)