The challenge
Return the anti-clockwise boundary, beginning at the root, without repeating nodes.
Convention: root, non-leaf left boundary, all leaves left to right, then reversed non-leaf right boundary.
Example
Balanced example: [8, 4, 2, 6, 10, 14, 12]. Right chain: [3, 1, 2].
Use the walkthrough below to inspect the input and each state change.
See Boundary, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Assign each boundary node to exactly one phase.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def boundary(root):
if root is None:
return []
def leaf(node):
return node.left is None and node.right is None
out = [root.value]
if leaf(root):
return out
node = root.left
while node:
if not leaf(node):
out.append(node.value)
node = node.left if node.left else node.right
def leaves(node):
if node is None:
return
if leaf(node):
out.append(node.value)
else:
leaves(node.left)
leaves(node.right)
leaves(root.left)
leaves(root.right)
right, node = [], root.right
while node:
if not leaf(node):
right.append(node.value)
node = node.right if node.right else node.left
out.extend(reversed(right))
return out
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
vector<long long> boundary(Node* root) {
if (!root) return {};
auto leaf = [](Node* n) { return !n->left && !n->right; };
vector<long long> out{root->value}, right;
if (leaf(root)) return out;
for (Node* n = root->left; n; n = n->left ? n->left : n->right)
if (!leaf(n)) out.push_back(n->value);
function<void(Node*)> leaves = [&](Node* n) {
if (!n) return;
if (leaf(n)) out.push_back(n->value);
else { leaves(n->left); leaves(n->right); }
};
leaves(root->left); leaves(root->right);
for (Node* n = root->right; n; n = n->right ? n->right : n->left)
if (!leaf(n)) right.push_back(n->value);
out.insert(out.end(), right.rbegin(), right.rend());
return out;
}