Boundary traversal of a Binary tree

The problem, simply

You get a binary tree. List the nodes on its outline, going around it the opposite way to a clock hand (counterclockwise), starting at the root:

1. The root.
2. The left edge, top to bottom, without the leaf at its end.
3. All the leaves, from left to right.
4. The right edge, bottom to top, without the leaf at its end.

Every node is listed once. The left edge starts at the root's left child and keeps going left; if a node has no left child, it steps to its right child. The right edge is the mirror of that.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do exactly what the ant does, in three separate walks.

1. Write the root, unless the root is a leaf (then the leaf walk will write it).
2. Left edge: start at root.left. While you are on a node, write it if it is not a leaf, then go left if you can, else go right.
3. Leaves: walk the whole tree left to right and write every leaf.
4. Right edge: start at root.right. Collect non-leaf nodes going right if you can, else left. Write them in reverse.

import java.util.*;

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

    public List<Integer> boundary(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        if (!isLeaf(root)) out.add(root.val);

        // left edge, top to bottom, no leaves
        for (TreeNode cur = root.left; cur != null; cur = (cur.left != null) ? cur.left : cur.right) {
            if (!isLeaf(cur)) out.add(cur.val);
        }

        addLeaves(root, out);

        // right edge, collected top to bottom, written bottom to top
        List<Integer> right = new ArrayList<>();
        for (TreeNode cur = root.right; cur != null; cur = (cur.right != null) ? cur.right : cur.left) {
            if (!isLeaf(cur)) right.add(cur.val);
        }
        for (int i = right.size() - 1; i >= 0; i--) out.add(right.get(i));
        return out;
    }

    private void addLeaves(TreeNode n, List<Integer> out) {
        if (n == null) return;
        if (isLeaf(n)) { out.add(n.val); return; }
        addLeaves(n.left, out);
        addLeaves(n.right, out);
    }
}

How long it takes: the edges are at most h nodes each and the leaf walk visits every node once, so O(n). Extra room: the leaf walk goes as deep as the tree, O(h). (The answer list itself is not counted.)

Way 2: the clever way

Do it in one walk. Give each helper two flags as it goes down: "am I on the left edge?" and "am I on the right edge?"

• A child stays on the left edge if its parent was on the left edge and it is the left child, or it is the right child and there is no left child.
• The right edge works the same way, mirrored.
• Write a node on the way in if it is on the left edge or is a leaf. That gives top to bottom for the left edge and left to right for the leaves.
• Write a right edge node on the way out, after both children are done. Coming back up gives bottom to top for free.

import java.util.*;

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

    public List<Integer> boundary(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        out.add(root.val);
        if (isLeaf(root)) return out;
        walk(root.left, true, false, out);
        walk(root.right, false, true, out);
        return out;
    }

    private void walk(TreeNode n, boolean leftEdge, boolean rightEdge, List<Integer> out) {
        if (n == null) return;
        if (leftEdge || isLeaf(n)) out.add(n.val);          // on the way in
        walk(n.left, leftEdge, rightEdge && n.right == null, out);
        walk(n.right, leftEdge && n.left == null, rightEdge, out);
        if (rightEdge && !leftEdge && !isLeaf(n)) out.add(n.val); // on the way out
    }
}

How long it takes: one visit per node, O(n). Extra room: the waiting helpers, as many as the tree is tall, O(h).

Watch out for

• The root alone. It is a leaf and the root at once. Write it once.
• No left child at the root. The left edge is empty. Do not start walking down the right side and call it the left edge.
• The edge must turn. When a left edge node has no left child, the edge continues to its right child.
• The right edge goes bottom to top. Reverse it, or write it on the way back up.

What interviewers ask next

• Can you do it without recursion? Yes. Use loops for both edges and a stack for the leaf walk.
• Clockwise instead? Start with the root, go down the right edge, the leaves from right to left, then up the left edge.
• Why not use the left view for the left edge? The left view picks the first node of each row, which can come from the right side of the tree. The boundary follows actual branches.
• How is this tested on LeetCode? It is problem 545, Boundary of Binary Tree, where the leftmost leaf must be counted as a leaf, the same rule as here.

Remember this

Grown-up words: the outline is the boundary traversal; the ant's walk is counterclockwise order; the helpers that wait are the recursion call stack; writing on the way out is post order.