The problem can be found at the following link: Problem Link
Given a binary tree, the task is to return a list of nodes representing its boundary traversal in an anticlockwise direction, starting from the root. The boundary includes:
- The left boundary (excluding the leaf nodes).
- All the leaf nodes (both from left and right subtrees).
- The right boundary (excluding the leaf nodes), added in reverse order.
Input:
root[] = [1, 2, 3, 4, 5, 6, 7, N, N, 8, 9, N, N, N, N]
Output:
[1, 2, 4, 8, 9, 6, 7, 3]
Input:
root[] = [1, 2, N, 4, 9, 6, 5, N, 3, N, N, N, N 7, 8]
Output:
[1, 2, 4, 6, 5, 7, 8]
Input:
root[] = [1, N, 2, N, 3, N, 4, N, N]
1
\
2
\
3
\
4
Output:
[1, 4, 3, 2]
Left boundary: [1] (as there is no left subtree)Leaf nodes: [4]Right boundary: [3, 2] (in reverse order)Final traversal: [1, 4, 3, 2]
- 1 <= Number of Nodes <=
$10^4$ - 1 <= Node Value <=
$10^5$
The boundary traversal of a binary tree consists of three parts:
-
Left Boundary:
- Traverse the leftmost nodes, excluding the leaf nodes.
- Move left whenever possible; otherwise, move right.
-
Leaf Nodes:
- Perform inorder traversal to collect leaf nodes.
-
Right Boundary:
- Traverse the rightmost nodes, excluding the leaf nodes.
- Move right whenever possible; otherwise, move left.
- Store nodes in a stack to reverse them before adding to the final result.
- Time Complexity:
O(N)Each node is visited at most once, so the time complexity is O(N). - Auxiliary Space Complexity:
O(H)(Height of the tree) The recursion stack space in a skewed tree can be O(N). In a balanced tree, it will be O(log N).
class Solution {
void lb(Node* r, vector<int>& v) {
if (!r || (!r->left && !r->right)) return;
v.push_back(r->data);
lb(r->left ? r->left : r->right, v);
}
void rb(Node* r, vector<int>& v) {
if (!r || (!r->left && !r->right)) return;
rb(r->right ? r->right : r->left, v);
v.push_back(r->data);
}
void leaf(Node* r, vector<int>& v) {
if (!r) return;
leaf(r->left, v);
if (!r->left && !r->right) v.push_back(r->data);
leaf(r->right, v);
}
public:
vector<int> boundaryTraversal(Node* r) {
if (!r) return {};
vector<int> v = {r->data};
lb(r->left, v);
leaf(r->left, v);
leaf(r->right, v);
rb(r->right, v);
return v;
}
};- Traverse the left boundary iteratively.
- Collect leaf nodes via BFS.
- Traverse the right boundary iteratively in reverse order.
class Solution {
public:
vector<int> boundaryTraversal(Node* root) {
if (!root) return {};
vector<int> res;
if (root->left || root->right) res.push_back(root->data);
Node* cur = root->left;
while (cur) {
if (cur->left || cur->right) res.push_back(cur->data);
cur = cur->left ? cur->left : cur->right;
}
function<void(Node*)> leafNodes = [&](Node* node) {
if (!node) return;
leafNodes(node->left);
if (!node->left && !node->right) res.push_back(node->data);
leafNodes(node->right);
};
leafNodes(root);
stack<int> rightBoundary;
cur = root->right;
while (cur) {
if (cur->left || cur->right) rightBoundary.push(cur->data);
cur = cur->right ? cur->right : cur->left;
}
while (!rightBoundary.empty()) {
res.push_back(rightBoundary.top());
rightBoundary.pop();
}
return res;
}
};- Use DFS traversal to visit nodes iteratively.
- Push the left boundary.
- Collect leaf nodes.
- Push the right boundary in reverse.
class Solution {
public:
vector<int> boundaryTraversal(Node* root) {
if (!root) return {};
vector<int> res;
if (root->left || root->right) res.push_back(root->data);
stack<Node*> s;
Node* cur = root->left;
while (cur) {
if (cur->left || cur->right) res.push_back(cur->data);
s.push(cur);
cur = cur->left ? cur->left : cur->right;
}
function<void(Node*)> leafNodes = [&](Node* node) {
if (!node) return;
leafNodes(node->left);
if (!node->left && !node->right) res.push_back(node->data);
leafNodes(node->right);
};
leafNodes(root);
stack<int> rightBoundary;
cur = root->right;
while (cur) {
if (cur->left || cur->right) rightBoundary.push(cur->data);
cur = cur->right ? cur->right : cur->left;
}
while (!rightBoundary.empty()) {
res.push_back(rightBoundary.top());
rightBoundary.pop();
}
return res;
}
};| Approach | Time Complexity | Space Complexity | Method | Pros | Cons |
|---|---|---|---|---|---|
| Recursive DFS | 🟢 O(N) | 🟡 O(H) | Recursion | Simple & structured | Stack overflow for deep trees |
| Iterative BFS | 🟢 O(N) | 🔴 O(W) | Queue-based | Avoids recursion depth issues | More memory for wide trees |
| Iterative DFS (Stack) | 🟢 O(N) | 🟡 O(H) | Stack-based | Explicit traversal order | Extra space for stack |
- For balanced trees, the Recursive DFS method is best.
- For deep trees, the Iterative BFS is preferable.
- For explicit iterative control, the DFS with Stack is an option.
class Solution {
void lb(Node r, ArrayList<Integer> v) {
if(r==null || (r.left==null && r.right==null)) return;
v.add(r.data);
lb(r.left!=null ? r.left : r.right, v);
}
void rb(Node r, ArrayList<Integer> v) {
if(r==null || (r.left==null && r.right==null)) return;
rb(r.right!=null ? r.right : r.left, v);
v.add(r.data);
}
void leaf(Node r, ArrayList<Integer> v) {
if(r==null)return;
leaf(r.left,v);
if(r.left==null && r.right==null) v.add(r.data);
leaf(r.right,v);
}
public ArrayList<Integer> boundaryTraversal(Node r) {
ArrayList<Integer> v = new ArrayList<>();
if(r==null)return v;
v.add(r.data);
lb(r.left, v);
leaf(r.left, v);
leaf(r.right, v);
rb(r.right, v);
return v;
}
}class Solution:
def boundaryTraversal(self, root):
if not root:
return []
res = [root.data] if root.left or root.right else []
cur = root.left
while cur:
if cur.left or cur.right:
res.append(cur.data)
cur = cur.left if cur.left else cur.right
def leaf_nodes(node):
if not node:
return
leaf_nodes(node.left)
if not node.left and not node.right:
res.append(node.data)
leaf_nodes(node.right)
leaf_nodes(root)
right_boundary = []
cur = root.right
while cur:
if cur.left or cur.right:
right_boundary.append(cur.data)
cur = cur.right if cur.right else cur.left
res += reversed(right_boundary)
return resFor discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
