Boundary Traversal of Binary Tree

Medium
1965.

Boundary Traversal of Binary Tree

Boundary Traversal of Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft and Flipkart interviews.

Given the root of a binary tree, return the values of its boundary in anticlockwise order, with no node listed twice:

  1. The root.
  2. 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.
  3. All the leaves (nodes with no children), from left to right.
  4. 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^5
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var boundaryTraversal = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

Problem statement

Given the root of a binary tree, return the values of its boundary in anticlockwise order, with no node listed twice:

  1. The root.
  2. 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.
  3. All the leaves (nodes with no children), from left to right.
  4. 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^5
  • 1 <= Node.val <= 10^5

Hints for Boundary Traversal of Binary Tree

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

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

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

  1. Output the root. If it is a leaf, stop.
  2. 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.
  3. Run a preorder DFS (left before right) from the root and output every leaf other than the root.
  4. Walk from root.right the 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 out

Java

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