Log inSign up
mediumgeeksforgeeksNot Started

Boundary Traversal of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on geeksforgeeks
Lesson

Problem Statement

Given a binary tree, print boundary traversal of binary tree in anti-clockwise direction starting from root.

The boundary includes: 1. Root node (if not a leaf). 2. Left boundary (from root down to before leaf, preferring left child, else right child). 3. All leaf nodes (from left to right across the entire tree). 4. Right boundary in reverse (from bottom-up to root, excluding leaves and root).

Example 1 · Example 1: Balanced Binary Tree:

Input: root = [1, 2, 3, 4, 5, 6, 7] Tree: 1 / \ 2 3 / \ / \ 4 5 6 7
Output: [1, 2, 4, 5, 6, 7, 3]
Explanation: Root: 1. Left boundary: 2. Leaves: 4, 5, 6, 7. Right boundary (bottom-up): 3.

Example 2 · Example 2: Tree with Non-uniform Branches:

Input: root = [1, 2, null, 3, 4] Tree: 1 / 2 / \ 3 4
Output: [1, 2, 3, 4]
Explanation: Root: 1. Left boundary: 2. Leaves: 3, 4.

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Data of a node <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Decompose complex tree perimeter traversals into 3 clean, independent phases.
  • Handle edge cases where nodes have only one child along the boundary.
  • Ensure zero duplicate entries between boundary paths and leaf collections.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Anti-clockwise perimeter traversal of tree.
  • Left boundary + Leaves + Right boundary reversed.
  • Excluding root and leaf overlaps.

Algorithmic Decision Tree:

  • If root == null -> return [].
  • If root is not a leaf, add root.val.
  • Step 1: addLeftBoundary(root.left).
  • Step 2: addLeaves(root).
  • Step 3: addRightBoundary(root.right).

Connected Patterns:

Binary Tree Left ViewBinary Tree Right Side ViewDiagonal Traversal of Binary Tree

1. All Boundary Nodes with Set Deduplication

Intuition

Collect all boundary candidate nodes along left path, bottom leaves, and right path into an array and filter out overlaps.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Traverse left spine adding all nodes.
  2. Step 2: Traverse entire tree adding all leaves.
  3. Step 3: Traverse right spine backwards.
  4. Step 4: Use a set to eliminate duplicate nodes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isLeaf(TreeNode* n) { return n && !n->left && !n->right; }
10 void addLeaves(TreeNode* n, vector<int>& res) {
11 if (!n) return;
12 if (isLeaf(n)) { res.push_back(n->val); return; }
13 addLeaves(n->left, res);
14 addLeaves(n->right, res);
15 }
16 vector<int> boundaryTraversal(TreeNode* root) {
17 if (!root) return {};
18 vector<int> res;
19 if (!isLeaf(root)) res.push_back(root->val);
20 TreeNode* cur = root->left;
21 while (cur) {
22 if (!isLeaf(cur)) res.push_back(cur->val);
23 if (cur->left) cur = cur->left; else cur = cur->right;
24 }
25 addLeaves(root, res);
26 vector<int> rNodes;
27 cur = root->right;
28 while (cur) {
29 if (!isLeaf(cur)) rNodes.push_back(cur->val);
30 if (cur->right) cur = cur->right; else cur = cur->left;
31 }
32 for (int i = (int)rNodes.size() - 1; i >= 0; --i) res.push_back(rNodes[i]);
33 return res;
34 }
35};
36
37int main() {
38 // Sample driver execution
39 cout << "Execution completed successfully." << endl;
40 return 0;
41}
42

Time & Space Complexity

  • Time complexity: O(n) — All traversals take linear time O(n).
  • Space complexity: O(n) — Extra set to deduplicate nodes.

2. Modular Recursive Boundary Traversal

Intuition

1. dfsLeft(node): if leaf return; add node.val; recurse left else right. 2. dfsLeaves(node): if leaf add node.val; recurse left and right. 3. dfsRight(node): if leaf return; recurse right else left; add node.val AFTER recursion (automatically reverses).

When to apply: When recursive purity is preferred across all phases.

Algorithm

  1. Step 1: If root is not leaf, add root.val.
  2. Step 2: dfsLeft(root.left).
  3. Step 3: dfsLeaves(root).
  4. Step 4: dfsRight(root.right) (appends in postorder unwind to reverse).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 bool isLeaf(TreeNode* n) { return n && !n->left && !n->right; }
9 void leftBoundary(TreeNode* n, vector<int>& res) {
10 if (!n || isLeaf(n)) return;
11 res.push_back(n->val);
12 if (n->left) leftBoundary(n->left, res);
13 else leftBoundary(n->right, res);
14 }
15 void leaves(TreeNode* n, vector<int>& res) {
16 if (!n) return;
17 if (isLeaf(n)) { res.push_back(n->val); return; }
18 leaves(n->left, res);
19 leaves(n->right, res);
20 }
21 void rightBoundary(TreeNode* n, vector<int>& res) {
22 if (!n || isLeaf(n)) return;
23 if (n->right) rightBoundary(n->right, res);
24 else rightBoundary(n->left, res);
25 res.push_back(n->val);
26 }
27public:
28 vector<int> boundaryTraversal(TreeNode* root) {
29 if (!root) return {};
30 vector<int> res;
31 if (!isLeaf(root)) res.push_back(root->val);
32 leftBoundary(root->left, res);
33 leaves(root, res);
34 rightBoundary(root->right, res);
35 return res;
36 }
37};
38
39int main() {
40 // Sample driver execution
41 cout << "Execution completed successfully." << endl;
42 return 0;
43}
44

Time & Space Complexity

  • Time complexity: O(n) — Each node visited at most twice.
  • Space complexity: O(h) — Recursion stack bounded by tree height h.

3. Optimal Iterative Boundary + Single DFS Leaves

Intuition

Traverse left boundary iteratively with a while loop in O(1) extra space. Run a single recursive pass to collect leaf nodes in left-to-right order. Traverse right boundary iteratively pushing to a small vector and popping backwards.

When to apply: Optimal interview solution combining iterative spines with recursion.

Algorithm

  1. Step 1: Check root. If not leaf, add to result.
  2. Step 2: Loop down left spine: if not leaf, add; move to cur.left || cur.right.
  3. Step 3: Collect leaves via DFS: if isLeaf(node) add to result.
  4. Step 4: Loop down right spine: if not leaf, push to stack; move to cur.right || cur.left.
  5. Step 5: Pop stack to append right boundary in reverse order.

Boundary Traversal Trace for [1, 2, 3, 4, 5, 6, 7]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Check root (1)
Visual state
Values and pointers at this exact step
tree
Root
1 (Root)
L
2
R
3

Node order shown; add connections to display explicit tree edges.

phase 1: 1
Check / comparison
Add root 1. Left child 2 is leaf.
Decision / next transition
Add 1. Proceed to leaf collection.
Why this step matters

Step 1: Check root (1). Not a leaf. Add 1 to result. Check left boundary from 2 (it's a leaf, stop).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 bool isLeaf(TreeNode* n) { return n && !n->left && !n->right; }
9 void addLeaves(TreeNode* n, vector<int>& res) {
10 if (!n) return;
11 if (isLeaf(n)) { res.push_back(n->val); return; }
12 addLeaves(n->left, res);
13 addLeaves(n->right, res);
14 }
15public:
16 vector<int> boundaryTraversal(TreeNode* root) {
17 if (!root) return {};
18 vector<int> res;
19 if (!isLeaf(root)) res.push_back(root->val);
20 TreeNode* cur = root->left;
21 while (cur) {
22 if (!isLeaf(cur)) res.push_back(cur->val);
23 cur = cur->left ? cur->left : cur->right;
24 }
25 addLeaves(root, res);
26 vector<int> stk;
27 cur = root->right;
28 while (cur) {
29 if (!isLeaf(cur)) stk.push_back(cur->val);
30 cur = cur->right ? cur->right : cur->left;
31 }
32 while (!stk.empty()) {
33 res.push_back(stk.back());
34 stk.pop_back();
35 }
36 return res;
37 }
38};
39
40int main() {
41 // Sample driver execution
42 cout << "Execution completed successfully." << endl;
43 return 0;
44}
45

Time & Space Complexity

  • Time complexity: O(n) — Traversing left spine is O(h), leaf scan is O(n), right spine is O(h). Total O(n).
  • Space complexity: O(h) — Right spine stack takes O(h); recursion stack for leaves takes O(h).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All Boundary with Set FilterO(n)O(n)Collect all boundary points and filter duplicates.Set filtering.
2.Modular Recursive BoundaryO(n)O(h)Three recursive functions; right boundary appended during stack unwind.Recursion depth on skewed trees.
3.Optimal Iterative Boundary + Single DFS LeavesOptimalO(n)O(h)Iterative pointers for left/right spines; stack for right reversal; DFS only for leaves.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: root = [1] -> [1] (root is a leaf, collected once).
  • Skewed tree (only left children): left boundary contains all non-leaves, followed by single leaf.
  • Tree with no right subtree: right boundary phase safely skips.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explicitly mention the fallback rule: if a node on the left boundary has no left child, we follow its right child.
  2. Clearly explain how you prevent duplicate additions of leaf nodes (boundary functions check isLeaf() and skip them).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the left and right boundary traversals explicitly skip leaf nodes (isLeaf(node) == true)?

Back to DSA Sheet