# LeetCode 545: Boundary of Binary Tree

## Problem Restatement

We are given the root of a binary tree.

We need to return the boundary of the tree in anti-clockwise order starting from the root.

The boundary consists of three parts:

1. Left boundary
2. Leaf nodes
3. Right boundary in reverse order

There are important rules:

| Part | Rule |
|---|---|
| Root | Included once |
| Left boundary | Exclude leaves |
| Leaves | Include all leaves from left to right |
| Right boundary | Exclude leaves and reverse order |
| Duplicates | No node should appear twice |

The left boundary is formed by always preferring the left child when moving downward. If no left child exists, move to the right child.

The right boundary similarly prefers the right child first.

The official problem defines the boundary as root, left boundary, leaves, and reversed right boundary, without duplicates. ([leetcode.com](https://leetcode.com/problems/boundary-of-binary-tree/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | Boundary node values in anti-clockwise order |
| Leaf rule | Include all leaves exactly once |
| Boundary rule | Exclude leaves from left/right boundaries |

Function shape:

```python
def boundaryOfBinaryTree(root: Optional[TreeNode]) -> list[int]:
    ...
```

## Examples

Consider:

```text
    1
     \
      2
     / \
    3   4
```

The boundary is:

```text
1 -> 3 -> 4 -> 2
```

Explanation:

| Part | Nodes |
|---|---|
| Root | `1` |
| Left boundary | none |
| Leaves | `3, 4` |
| Right boundary reversed | `2` |

Output:

```python
[1, 3, 4, 2]
```

Another example:

```text
        1
       / \
      2   3
     / \   \
    4   5   6
       / \  /
      7  8 9
```

Boundary traversal:

| Part | Nodes |
|---|---|
| Root | `1` |
| Left boundary | `2` |
| Leaves | `4, 7, 8, 9` |
| Right boundary reversed | `6, 3` |

Final order:

```python
[1, 2, 4, 7, 8, 9, 6, 3]
```

## First Thought: One DFS Around the Tree

A natural idea is to walk around the outside of the tree.

But handling all cases in one traversal becomes complicated:

- Leaves may appear on both sides.
- Left and right boundaries must exclude leaves.
- Right boundary must be reversed.
- Nodes must not repeat.

A cleaner solution is to treat each part independently.

## Key Insight

The boundary can be built in exactly this order:

```text
root
+
left boundary
+
all leaves
+
reversed right boundary
```

Each part has a simple rule.

So instead of trying to solve everything in one DFS, we write three separate traversals:

1. Add left boundary
2. Add leaves
3. Add right boundary

This keeps the logic easy to verify.

## Algorithm

1. If the tree is empty, return `[]`.
2. Add the root value.
3. Traverse the left boundary:
   - Prefer left child.
   - Otherwise use right child.
   - Skip leaves.
4. Traverse all leaves:
   - DFS over the whole tree.
   - Add only leaf nodes.
5. Traverse the right boundary:
   - Prefer right child.
   - Otherwise use left child.
   - Skip leaves.
   - Add nodes in reverse order.
6. Return the result.

## Correctness

The algorithm adds nodes in exactly the required anti-clockwise boundary order.

The root is added first.

The left boundary traversal starts from the root's left child and always moves downward along the outer edge of the tree. Leaf nodes are excluded so they are not duplicated later during leaf collection.

The leaf traversal visits every node in the tree and adds exactly those nodes with no children. Since every leaf is visited once and boundary traversals skip leaves, each leaf appears exactly once in the final result.

The right boundary traversal follows the outer right edge of the tree, excluding leaves. Nodes are collected during downward traversal and then appended in reverse order, which produces the required bottom-up right boundary order.

Every boundary node belongs to exactly one of these categories:

- root
- left boundary
- leaf
- right boundary

and the traversal rules prevent duplicates between categories.

Therefore, the algorithm returns the correct tree boundary in anti-clockwise order.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Every node is visited at most a constant number of times |
| Space | `O(h)` | Recursion stack height |

`h` is the tree height.

In a balanced tree:

```python
h = O(log n)
```

In a skewed tree:

```python
h = O(n)
```

## Implementation

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        def is_leaf(node: TreeNode) -> bool:
            return node.left is None and node.right is None

        boundary = [root.val]

        def add_left_boundary(node: Optional[TreeNode]) -> None:
            while node:
                if not is_leaf(node):
                    boundary.append(node.val)

                if node.left:
                    node = node.left
                else:
                    node = node.right

        def add_leaves(node: Optional[TreeNode]) -> None:
            if node is None:
                return

            if is_leaf(node):
                boundary.append(node.val)
                return

            add_leaves(node.left)
            add_leaves(node.right)

        def add_right_boundary(node: Optional[TreeNode]) -> None:
            stack = []

            while node:
                if not is_leaf(node):
                    stack.append(node.val)

                if node.right:
                    node = node.right
                else:
                    node = node.left

            while stack:
                boundary.append(stack.pop())

        add_left_boundary(root.left)

        if not is_leaf(root):
            add_leaves(root)

        add_right_boundary(root.right)

        return boundary
```

## Code Explanation

We first handle the empty tree:

```python
if root is None:
    return []
```

The helper:

```python
is_leaf(node)
```

checks whether a node has no children.

The root is always included first:

```python
boundary = [root.val]
```

### Left Boundary

The left boundary traversal moves downward:

```python
if node.left:
    node = node.left
else:
    node = node.right
```

This follows the outermost edge.

Leaves are skipped:

```python
if not is_leaf(node):
```

because leaves are handled separately.

### Leaves

The leaf traversal performs DFS over the entire tree.

If a node is a leaf:

```python
if is_leaf(node):
    boundary.append(node.val)
```

Otherwise we continue recursively.

### Right Boundary

The right boundary traversal is similar to the left boundary, but it prefers the right child first.

The important difference is that right-boundary nodes must appear bottom-up.

So we first collect them into a stack:

```python
stack.append(node.val)
```

Then reverse the order by popping:

```python
while stack:
    boundary.append(stack.pop())
```

## Edge Cases

### Single Node

```text
1
```

The root is also a leaf.

Output:

```python
[1]
```

The code avoids duplicate insertion because:

```python
if not is_leaf(root):
    add_leaves(root)
```

### Left-Skewed Tree

```text
    1
   /
  2
 /
3
```

Boundary:

```python
[1, 2, 3]
```

### Right-Skewed Tree

```text
1
 \
  2
   \
    3
```

Boundary:

```python
[1, 3, 2]
```

The right boundary is reversed.

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(
        1,
        None,
        TreeNode(2, TreeNode(3), TreeNode(4)),
    )
    assert s.boundaryOfBinaryTree(root) == [1, 3, 4, 2]

    root = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(4),
            TreeNode(5, TreeNode(7), TreeNode(8)),
        ),
        TreeNode(
            3,
            None,
            TreeNode(6, TreeNode(9), None),
        ),
    )
    assert s.boundaryOfBinaryTree(root) == [1, 2, 4, 7, 8, 9, 6, 3]

    root = TreeNode(1)
    assert s.boundaryOfBinaryTree(root) == [1]

    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert s.boundaryOfBinaryTree(root) == [1, 2, 3]

    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    assert s.boundaryOfBinaryTree(root) == [1, 3, 2]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Root with right subtree | Checks missing left boundary |
| Mixed full tree | Standard complete boundary traversal |
| Single node | Checks duplicate prevention |
| Left-skewed tree | Checks left boundary logic |
| Right-skewed tree | Checks reversed right boundary |