On this page

Boundary Traversal

Given a binary tree, return its boundary traversal in anti-clockwise order starting from the root:

  1. The left boundary (top to bottom), excluding leaves.
  2. All the leaf nodes (left to right).
  3. The right boundary (bottom to top), excluding leaves.

The root is included once at the start.

Intuition

1 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Here 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.

  1. 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.)
  2. 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.
  3. Leaves: a normal DFS from the root that adds any node that is a leaf. This picks up leaves in left to right order.
  4. 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

Time: O(n)

The left and right boundary walks together touch at most one root-to-leaf path each, and the leaf DFS touches every node once.

Space: O(h)

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.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The boundary is three pieces in order: the left boundary excluding leaves, then all the leaves left to right, then the right boundary excluding leaves, in reverse. First I add the root, but only if it is not a leaf, because a lone root leaf is added by the leaf pass. For the left boundary I walk down from the left child, adding non-leaf nodes and preferring the left child, falling back to the right. The leaves come from a simple DFS. For the right boundary I do the mirror walk into a temporary list and append it reversed so it reads bottom to top. Skipping leaves in both boundary walks is what prevents duplicates. Time is O of n and extra space is O of h."
Next TopicVertical Order Traversal