Sum of the Node Values on a Binary Tree's Boundary
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Picture walking around the outside of a binary tree, starting at the root: you go down the left edge, along the leaves at the bottom from left to right, and back up the right edge. The nodes you pass form the tree's boundary.
Given a binary tree of integers, return the sum of the values of its boundary nodes. Each node counts at most once.
### Function Signature
```python
def boundary_sum(tree: list[int | None]) -> int:
```
`tree` is the tree in level order, and `tree[0]` is the root. Nodes receive their children in the order they appear in the list: the root takes the next two entries as its left child and right child, then the next present node in the list takes the following two entries, and so on. `None` means that the child is absent, and a `None` entry takes no entries of its own. If the list ends early, the remaining children are absent.
### Rules
- The root is on the boundary. The root is never treated as a leaf, even when it has no children.
- A leaf is any node other than the root that has no children. Every leaf is on the boundary.
- The left edge starts at the root's left child; if the root has no left child, the left edge is empty. From a node on the left edge that is not a leaf, the edge continues to that node's left child if it has one, and otherwise to its right child. The walk stops when it reaches a leaf, which is counted as a leaf and not again as part of the left edge.
- The right edge is the mirror image: it starts at the root's right child (it is empty if there is none) and continues to a node's right child if it has one, and otherwise to its left child, stopping at a leaf.
- Every node that is not the root, a leaf, or on one of the two edges is interior and is not counted.
- Return the sum of the values of the root, the left-edge nodes, the leaves and the right-edge nodes.
### Constraints
- `1 <= number of nodes <= 10^4`, and `tree[0]` is not `None`.
- `len(tree) <= 2 * 10^4 + 1`
- `-1000 <= node value <= 1000`
- The tree may be completely skewed, so its height can equal the number of nodes.
- The absolute value of the answer is at most `10^7`, so it fits in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: tree = [1, 2, 3, 4, 5, 6, None, None, None, 7, 8, 9, 10]
Output: 50
```
The root 1 has children 2 and 3. Node 2 has children 4 and 5, and node 3 has only a left child, 6. Node 4 is a leaf, node 5 has children 7 and 8, and node 6 has children 9 and 10.
The left edge is just 2, because its left child 4 is a leaf. The leaves from left to right are 4, 7, 8, 9 and 10. The right edge is 3 and then 6, because 3 has no right child; the walk stops at 6's right child 10, which is a leaf. Node 5 is interior. The sum is 1 + 2 + 4 + 7 + 8 + 9 + 10 + 6 + 3 = 50.
**Example 2**
```text
Input: tree = [1, None, 2, 3, 4, 5, 6]
Output: 18
```
The root 1 has only a right child, 2. Node 2 has children 3 and 4, and node 3 has children 5 and 6. Because the root has no left child, the left edge is empty, so node 3 is not on it. The leaves are 5, 6 and 4, and the right edge is just 2, because its right child 4 is a leaf. Node 3 is interior. The sum is 1 + 5 + 6 + 4 + 2 = 18.
**Example 3**
```text
Input: tree = [-7]
Output: -7
```
A single node is the root. It is not a leaf, so it is counted exactly once.
Overview: A binary tree coding problem: given a tree in level-order form, add up the values of the nodes on its boundary, meaning the root, the left edge, the leaves and the right edge, each counted once. It tests precise traversal rules, careful edge definitions and correct handling of skewed and single-node trees.
Read the full Snowflake Software Engineer interview experience this question came from
Picture walking around the outside of a binary tree, starting at the root: you go down the left edge, along the leaves at the bottom from left to right, and back up the right edge. The nodes you pass form the tree's boundary.
Given a binary tree of integers, return the sum of the values of its boundary nodes. Each node counts at most once.
**Input format**
`tree` is the tree in level order, and `tree[0]` is the root. Nodes receive their children in the order they appear in the list: the root takes the next two entries as its left child and right child, then the next present node in the list takes the following two entries, and so on. `None` means that the child is absent, and a `None` entry takes no entries of its own. If the list ends early, the remaining children are absent. The list is a valid level-order encoding, so every non-`None` entry is a node of the tree. An absent entry is `None` in Python, `null` in JavaScript and in the Java `java.util.List<Integer>`, and an empty `std::optional<int>` in C++.
**Rules**
- The root is on the boundary. The root is never treated as a leaf, even when it has no children.
- A leaf is any node other than the root that has no children. Every leaf is on the boundary.
- The left edge starts at the root's left child; if the root has no left child, the left edge is empty. From a node on the left edge that is not a leaf, the edge continues to that node's left child if it has one, and otherwise to its right child. The walk stops when it reaches a leaf, which is counted as a leaf and not again as part of the left edge.
- The right edge is the mirror image: it starts at the root's right child (it is empty if there is none) and continues to a node's right child if it has one, and otherwise to its left child, stopping at a leaf.
- Every node that is not the root, a leaf, or on one of the two edges is interior and is not counted.
- Return the sum of the values of the root, the left-edge nodes, the leaves and the right-edge nodes.
**Example 1**
```
Input: tree = [1, 2, 3, 4, 5, 6, None, None, None, 7, 8, 9, 10]
Output: 50
```
The root 1 has children 2 and 3. Node 2 has children 4 and 5, and node 3 has only a left child, 6. Node 4 is a leaf, node 5 has children 7 and 8, and node 6 has children 9 and 10. The left edge is just 2, because its left child 4 is a leaf. The leaves from left to right are 4, 7, 8, 9 and 10. The right edge is 3 and then 6, because 3 has no right child; the walk stops at 6's right child 10, which is a leaf. Node 5 is interior. The sum is 1 + 2 + 4 + 7 + 8 + 9 + 10 + 6 + 3 = 50.
**Example 2**
```
Input: tree = [1, None, 2, 3, 4, 5, 6]
Output: 18
```
The root 1 has only a right child, 2. Node 2 has children 3 and 4, and node 3 has children 5 and 6. Because the root has no left child, the left edge is empty, so node 3 is not on it. The leaves are 5, 6 and 4, and the right edge is just 2, because its right child 4 is a leaf. Node 3 is interior. The sum is 1 + 5 + 6 + 4 + 2 = 18.
**Constraints**
- `1 <= number of nodes <= 10^4`, and `tree[0]` is not `None`.
- `len(tree) <= 2 * 10^4 + 1`
- `-1000 <= node value <= 1000`
- The tree may be completely skewed, so its height can equal the number of nodes.
- The absolute value of the answer is at most `10^7`, so it fits in a signed 32-bit integer: it never exceeds 2^31 - 1, and `int` is enough in Java and C++.
Constraints
- 1 <= number of nodes <= 10^4, and tree[0] is not None.
- len(tree) <= 2 * 10^4 + 1
- -1000 <= node value <= 1000
- The tree may be completely skewed, so its height can equal the number of nodes.
- The absolute value of the answer is at most 10^7, so it fits in a signed 32-bit integer.
Examples
Input: ([1, 2, 3, 4, 5, 6, None, None, None, 7, 8, 9, 10],)
Expected Output: 50
Explanation: Source Example 1: left edge 2, leaves 4, 7, 8, 9, 10, right edge 3 then 6 (falls through to the left child); node 5 is interior. 1+2+4+7+8+9+10+6+3 = 50.
Input: ([1, None, 2, 3, 4, 5, 6],)
Expected Output: 18
Explanation: Source Example 2: the root has no left child, so the left edge is empty and node 3 is interior; 1+5+6+4+2 = 18.
Hints
- Rebuild the child links first: only present nodes claim entries, they claim them two at a time in the order they appear in the list, and a None entry claims nothing.
- Whether a non-root node is a leaf depends only on its own children, so the leaves can be identified without knowing where the two edges run.
- The tree can be 10^4 levels deep, so make sure any walk over it does not rely on deep recursion.