Boundary Traversal
Given a binary tree, return its boundary traversal in anti-clockwise order starting from the root:
- The left boundary (top to bottom), excluding leaves.
- All the leaf nodes (left to right).
- The right boundary (bottom to top), excluding leaves.
The root is included once at the start.
Intuition
1 12 / \3 2 34 / \ \5 4 5 6Here the boundary is 1, 2, 4, 5, 6, 3:
- Root: 1
- Left boundary (no leaves): 2
- Leaves, left to right: 4, 5, 6
- Right boundary, bottom to top (no leaves): 3
The boundary is three separate pieces. Do each piece on its own and glue them together in order. The only care needed is to avoid adding a node twice, especially leaves, which belong to the middle piece only.
Approach: Three Parts
Define isLeaf(node) as a node with no left and no right child.
- If the root is not a leaf, add it. (If it is a leaf, the leaf pass will add it, so adding it now would duplicate it.)
- Left boundary: start at
root.left. While the node exists: if it is not a leaf, add it. Then go to its left child, or to its right child if there is no left child. - Leaves: a normal DFS from the root that adds any node that is a leaf. This picks up leaves in left to right order.
- Right boundary: same walk as the left boundary but on
root.right, preferring the right child. Collect into a temporary list and add it in reverse, so it reads bottom to top.
Skipping leaves in steps 2 and 4 is what keeps each node in the answer exactly once.
Code
class Solution {bool isLeaf(Node* node) {return node->left == nullptr && node->right == nullptr;}void addLeftBoundary(Node* root, vector<int>& ans) {Node* cur = root->left;while (cur != nullptr) {if (!isLeaf(cur)) ans.push_back(cur->data);cur = cur->left != nullptr ? cur->left : cur->right;}}void addLeaves(Node* node, vector<int>& ans) {if (node == nullptr) return;if (isLeaf(node)) {ans.push_back(node->data);return;}addLeaves(node->left, ans);addLeaves(node->right, ans);}void addRightBoundary(Node* root, vector<int>& ans) {Node* cur = root->right;vector<int> temp;while (cur != nullptr) {if (!isLeaf(cur)) temp.push_back(cur->data);cur = cur->right != nullptr ? cur->right : cur->left;}for (int i = temp.size() - 1; i >= 0; i--) ans.push_back(temp[i]);}public:vector<int> boundary(Node* root) {vector<int> ans;if (root == nullptr) return ans;if (!isLeaf(root)) ans.push_back(root->data);addLeftBoundary(root, ans);addLeaves(root, ans);addRightBoundary(root, ans);return ans;}};
Complexity
The left and right boundary walks together touch at most one root-to-leaf path each, and the leaf DFS touches every node once.
Recursion stack for the leaf pass is O(h). The temporary list for the right boundary is also at most O(h). The output is not counted.