0545.md

545. Boundary of Binary Tree

Level:

Topic:

Question

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary.

Input: root = [1,null,2,3,4]
Output: [1,3,4,2]
Explanation:

• The left boundary is empty because the root does not have a left child.
• The right boundary follows the path starting from the root's right child 2 -> 4. 4 is a leaf, so the right boundary is [2].
• The leaves from left to right are [3,4]. Concatenating everything results in [1] + [] + [3,4] + [2] = [1,3,4,2].

Intuition

Iterative:

• add the root
• add left boundary
• add leafs (any traversal)
• add right boundary using stack

Code

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

Recursive

private boolean isLeaf(TreeNode node) {
    return node.left == null && node.right == null;
}

List<Integer> ans = new ArrayList<>();
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
    if (root == null) return ans;
    // add root to list
    if (!isLeaf(root)) ans.add(root.val);

    // add left boundary nodes
    // not to start with root so it wouldn't interfere with right subtree
    TreeNode curr = root.left;
    while (curr != null) {
        if (isLeaf(curr)) break;
        ans.add(curr.val);
        curr = curr.left != null ? curr.left:curr.right;
    }

    addLeaves(root); // add all leaf nodes

    // add right boundary nodes, in reversed order so use stack
    // not to start with root so it wouldn't interfere with left subtree
    Stack<Integer> stack = new Stack<>();
    curr = root.right;
    while (curr != null) {
        if (isLeaf(curr)) break;
        stack.push(curr.val);
        curr = curr.right != null ? curr.right:curr.left;
    }
    while (!stack.isEmpty())
        ans.add(stack.pop());
    return ans;
}

void addLeaves(TreeNode root) {
    if (root == null) return;
    if (isLeaf(root)) ans.add(root.val);
    addLeaves(root.left);
    addLeaves(root.right);
}