class Solution:
def boundaryOfBinaryTree(self, root):
if not root:
return []
res = []
def isLeaf(node):
return node and not node.left and not node.right
def addLeftBoundary(node):
while node:
if not isLeaf(node):
res.append(node.val)
node = node.left if node.left else node.right
def addLeaves(node):
if node:
if isLeaf(node):
res.append(node.val)
else:
addLeaves(node.left)
addLeaves(node.right)
def addRightBoundary(node):
tmp = []
while node:
if not isLeaf(node):
tmp.append(node.val)
node = node.right if node.right else node.left
res.extend(reversed(tmp))
if not isLeaf(root):
res.append(root.val)
addLeftBoundary(root.left)
addLeaves(root)
addRightBoundary(root.right)
return res
class Solution {
public:
vector<int> boundaryOfBinaryTree(TreeNode* root) {
vector<int> res;
if (!root) return res;
if (!isLeaf(root)) res.push_back(root->val);
addLeftBoundary(root->left, res);
addLeaves(root, res);
addRightBoundary(root->right, res);
return res;
}
private:
bool isLeaf(TreeNode* node) {
return node && !node->left && !node->right;
}
void addLeftBoundary(TreeNode* node, vector<int>& res) {
while (node) {
if (!isLeaf(node)) res.push_back(node->val);
node = node->left ? node->left : node->right;
}
}
void addLeaves(TreeNode* node, vector<int>& res) {
if (node) {
if (isLeaf(node)) res.push_back(node->val);
else {
addLeaves(node->left, res);
addLeaves(node->right, res);
}
}
}
void addRightBoundary(TreeNode* node, vector<int>& res) {
vector<int> tmp;
while (node) {
if (!isLeaf(node)) tmp.push_back(node->val);
node = node->right ? node->right : node->left;
}
for (int i = tmp.size() - 1; i >= 0; --i)
res.push_back(tmp[i]);
}
};
class Solution {
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
if (!isLeaf(root)) res.add(root.val);
addLeftBoundary(root.left, res);
addLeaves(root, res);
addRightBoundary(root.right, res);
return res;
}
private boolean isLeaf(TreeNode node) {
return node != null && node.left == null && node.right == null;
}
private void addLeftBoundary(TreeNode node, List<Integer> res) {
while (node != null) {
if (!isLeaf(node)) res.add(node.val);
node = node.left != null ? node.left : node.right;
}
}
private void addLeaves(TreeNode node, List<Integer> res) {
if (node != null) {
if (isLeaf(node)) res.add(node.val);
else {
addLeaves(node.left, res);
addLeaves(node.right, res);
}
}
}
private void addRightBoundary(TreeNode node, List<Integer> res) {
List<Integer> tmp = new ArrayList<>();
while (node != null) {
if (!isLeaf(node)) tmp.add(node.val);
node = node.right != null ? node.right : node.left;
}
for (int i = tmp.size() - 1; i >= 0; --i)
res.add(tmp.get(i));
}
}
var boundaryOfBinaryTree = function(root) {
if (!root) return [];
const res = [];
function isLeaf(node) {
return node && !node.left && !node.right;
}
function addLeftBoundary(node) {
while (node) {
if (!isLeaf(node)) res.push(node.val);
node = node.left ? node.left : node.right;
}
}
function addLeaves(node) {
if (node) {
if (isLeaf(node)) res.push(node.val);
else {
addLeaves(node.left);
addLeaves(node.right);
}
}
}
function addRightBoundary(node) {
const tmp = [];
while (node) {
if (!isLeaf(node)) tmp.push(node.val);
node = node.right ? node.right : node.left;
}
for (let i = tmp.length - 1; i >= 0; --i)
res.push(tmp[i]);
}
if (!isLeaf(root)) res.push(root.val);
addLeftBoundary(root.left);
addLeaves(root);
addRightBoundary(root.right);
return res;
};
Each node value should appear only once in the boundary. Do not duplicate leaves or root.
The input is a binary tree represented by the root node. The output is a list of integers representing the boundary in the specified order.
At first glance, the problem seems to ask for a traversal, but not a standard preorder, inorder, or postorder. Instead, we need to carefully walk along the "edge" of the tree, collecting nodes in a particular order and avoiding duplicates.
A brute-force approach might try to traverse the tree multiple times or use extra data structures to track duplicates, but this can get messy. Instead, it's better to break the problem into three clear steps: collect the left boundary, collect the leaves, and collect the right boundary (in reverse), ensuring no node is added twice.
root.left, traverse downward. At each step, add the node's value if it's not a leaf. Prefer left children; if none, go right. Stop when you reach a leaf or null.
root.right, traverse downward. At each step, add the node's value to a temporary list if it's not a leaf (to avoid duplication). Prefer right children; if none, go left. After traversal, reverse this temporary list and append it to the result, ensuring bottom-up order.
We use helper functions for each part (left boundary, leaves, right boundary) to keep the code modular and readable. This approach is both efficient and easy to understand.
Consider the following binary tree:
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
1 to the result.
2 down. Add 2 (not a leaf). Next, go to 4 (a leaf), so stop.
4, 7, 8, 6.
3 down. 3 is not a leaf, add to temp list. Go to 6 (a leaf), so stop. Reverse the temp list ([3]) and add to result.
Final boundary order: [1, 2, 4, 7, 8, 6, 3]
By breaking the problem into three distinct traversals—left boundary, leaves, and right boundary—we can efficiently collect the boundary of a binary tree in anti-clockwise order without duplicating nodes. The solution uses clear helper functions to keep logic modular and readable, and handles edge cases naturally. This approach is both optimal and elegant, making the problem approachable for programmers at any level.