Boundary Traversal of Binary Tree — Problem & Solution
Boundary Traversal of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Boundary Traversal of Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft and Flipkart interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the values of its boundary in anticlockwise order, with no node listed twice:
- The root.
- The left boundary without its leaf: start at the root's left child and keep moving to the left child, or to the right child when there is no left one, stopping before the first leaf. If the root has no left child, this part is empty.
- All the leaves (nodes with no children), from left to right.
- The right boundary without its leaf, bottom-up: built like the left boundary from the root's right child, preferring the right child, then listed in reverse. If the root has no right child, this part is empty.
If the root itself is a leaf, the answer is just the root.
Example 1
Input: root = [1,2,3,4,5,6,7,null,null,8,9]
Output: [1,2,4,8,9,6,7,3]
Explanation: Root 1; left boundary 2 (4 is a leaf); leaves 4, 8, 9, 6, 7; right boundary 3 read bottom-up.
Example 2
Input: root = [1,2,null,4,9,6,5,null,3,null,null,null,null,7,8]
Output: [1,2,4,6,5,7,8]
Explanation: There is no right subtree, so the boundary is the root, the left edge 2, 4, the leaves 6, 5, 7, 8 and nothing more — 9 is on the inside and not a leaf.
Example 3
Input: root = [1,null,2,null,3]
Output: [1,3,2]
Explanation: No left subtree: after the root comes the only leaf 3, then the right edge 2 read upwards.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5
Hints for Boundary Traversal of Binary Tree
Hint 1
Split the answer into four parts that never overlap: the root, the left edge without leaves, the leaves, and the right edge without leaves.
Hint 2
The two edges are simple walks: down the left side preferring left children, down the right side preferring right children — stop at a leaf, since leaves are listed separately.
Hint 3
Collect leaves with a depth-first traversal that visits left before right; reverse the right edge before appending it.
How to solve Boundary Traversal of Binary Tree
Treat the boundary as four disjoint lists built in order: the root, the left edge's internal nodes top-down, every leaf left to right, and the right edge's internal nodes bottom-up.
Approach
- Output the root. If it is a leaf, stop.
- Walk from
root.left: while the node is not a leaf, output it and move to its left child, or its right child if there is no left one. - Run a preorder DFS (left before right) from the root and output every leaf other than the root.
- Walk from
root.rightthe same way preferring right children, collecting non-leaf nodes; output them in reverse.
Why it works
Each node is listed in at most one part: the edges skip leaves, the leaf pass lists only leaves, and the root is excluded from both edges (they start at its children). A preorder DFS reaches leaves in left-to-right order, and reversing the right edge produces the anticlockwise direction up the right side.
Complexity
- Time —
O(n) - Space —
O(h) for the DFS plus the output
Pitfalls
- Leaves at the bottom of the left or right edge must not be listed twice — stop each edge walk before a leaf.
- When the root has no left child, the left edge is empty; do not walk down the right subtree instead.
- A root that is a leaf appears once, not again among the leaves.
Reference solution
Python
from typing import List, Optional
def boundaryTraversal(root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
def leaf(n):
return n.left is None and n.right is None
out = [root.val]
if leaf(root):
return out
cur = root.left
while cur and not leaf(cur):
out.append(cur.val)
cur = cur.left if cur.left else cur.right
stack = [root]
while stack:
node = stack.pop()
if node is not root and leaf(node):
out.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
right = []
cur = root.right
while cur and not leaf(cur):
right.append(cur.val)
cur = cur.right if cur.right else cur.left
out.extend(reversed(right))
return outJava
public static int[] boundaryTraversal(TreeNode root) {
List<Integer> out = new ArrayList<>();
if (root == null) return new int[0];
out.add(root.val);
if (root.left != null || root.right != null) {
TreeNode cur = root.left;
while (cur != null && (cur.left != null || cur.right != null)) {
out.add(cur.val);
cur = cur.left != null ? cur.left : cur.right;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != root && node.left == null && node.right == null) out.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
List<Integer> right = new ArrayList<>();
cur = root.right;
while (cur != null && (cur.left != null || cur.right != null)) {
right.add(cur.val);
cur = cur.right != null ? cur.right : cur.left;
}
for (int i = right.size() - 1; i >= 0; i--) out.add(right.get(i));
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
static bool isLeafNode(TreeNode* n);
vector<int> boundaryTraversal(TreeNode* root) {
vector<int> out;
if (!root) return out;
out.push_back(root->val);
if (isLeafNode(root)) return out;
TreeNode* cur = root->left;
while (cur && !isLeafNode(cur)) {
out.push_back(cur->val);
cur = cur->left ? cur->left : cur->right;
}
vector<TreeNode*> stack = {root};
while (!stack.empty()) {
TreeNode* node = stack.back();
stack.pop_back();
if (node != root && isLeafNode(node)) out.push_back(node->val);
if (node->right) stack.push_back(node->right);
if (node->left) stack.push_back(node->left);
}
vector<int> right;
cur = root->right;
while (cur && !isLeafNode(cur)) {
right.push_back(cur->val);
cur = cur->right ? cur->right : cur->left;
}
out.insert(out.end(), right.rbegin(), right.rend());
return out;
}
static bool isLeafNode(TreeNode* n) {
return !n->left && !n->right;
}JavaScript
var boundaryTraversal = function(root) {
if (root === null) return [];
var leaf = function(n) { return n.left === null && n.right === null; };
var out = [root.val];
if (leaf(root)) return out;
var cur = root.left;
while (cur !== null && !leaf(cur)) {
out.push(cur.val);
cur = cur.left !== null ? cur.left : cur.right;
}
var stack = [root];
while (stack.length > 0) {
var node = stack.pop();
if (node !== root && leaf(node)) out.push(node.val);
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
var right = [];
cur = root.right;
while (cur !== null && !leaf(cur)) {
right.push(cur.val);
cur = cur.right !== null ? cur.right : cur.left;
}
for (var i = right.length - 1; i >= 0; i--) out.push(right[i]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals