Boundary of Binary Tree

Medium Trees & BST Views Original on LeetCode

Reported atSnowflakeNutanix

Boundary of Binary Tree is a medium trees & bst problem solved with the views pattern. The best approach, optimal (one dfs with boundary flags), runs in O(n) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from three separate walks up.

Problem

The boundary of a binary tree is the sequence you get by walking around its outside counter-clockwise, starting at the root. It is made of four parts, concatenated in this order without duplicates:

  1. The root.
  2. The left boundary: start at the root’s left child and keep moving to the left child (or to the right child when there is no left child), stopping before you reach a leaf. If the root has no left child, this part is empty. Leaves are not included here.
  3. All the leaves, from left to right. The root itself is not considered a leaf here unless it is the only node, in which case it is listed just once.
  4. The right boundary in reverse (bottom to top): defined like the left boundary, but starting at the root’s right child and preferring right children. Leaves are not included.

Given the root of a binary tree, return the values of its boundary in this order.

Examples

Example 1

Input
root = [10, 4, 12, 2, 6, null, 15, null, null, 5, 7, 14]
Output
[10, 4, 2, 5, 7, 14, 15, 12]
Why
Root 10; left boundary 4 (2 is a leaf); leaves 2, 5, 7, 14; right boundary bottom-up 15, 12 (14 is a leaf, so it was already listed).

Example 2

Input
root = [3, null, 8, 6, 9]
Output
[3, 6, 9, 8]
Why
There is no left child, so the left boundary is empty. Leaves are 6 and 9, and the right boundary is just 8.

Example 3

Input
root = [1]
Output
[1]
Why
A lone root is reported once and is not treated as a leaf a second time.

Constraints

  • The number of nodes is in the range [1, 10^4].
  • -1000 <= Node.val <= 1000

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Three separate walksO(n)O(n)
Optimal (one DFS with boundary flags)O(n)O(h)

1Three separate walks

TimeO(n)The leaf DFS visits every node once; the two walks are at most the height.
SpaceO(n)Recursion depth and the right-boundary stack are O(h), which is O(n) for a skewed tree.

Build the answer piece by piece: the root, then walk down the left edge (preferring left children) adding non-leaves, then add every leaf with a DFS, then walk down the right edge (preferring right children) collecting non-leaves and append them in reverse.

  1. Add the root. If it is a leaf, stop.
  2. Left walk from root.left: add the node if it is not a leaf, then move to its left child, or its right child if there is no left one.
  3. DFS over the whole tree, adding leaves in left-to-right order.
  4. Right walk from root.right mirroring the left walk; push non-leaves on a stack and pop them into the answer.
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        res.add(root.val);
        if (isLeaf(root)) return res;
        TreeNode cur = root.left;
        while (cur != null) {
            if (!isLeaf(cur)) res.add(cur.val);
            cur = cur.left != null ? cur.left : cur.right;
        }
        addLeaves(root, res);
        Deque<Integer> stack = new ArrayDeque<>();
        cur = root.right;
        while (cur != null) {
            if (!isLeaf(cur)) stack.push(cur.val);
            cur = cur.right != null ? cur.right : cur.left;
        }
        while (!stack.isEmpty()) res.add(stack.pop());
        return res;
    }

    private boolean isLeaf(TreeNode n) {
        return n.left == null && n.right == null;
    }

    private void addLeaves(TreeNode n, List<Integer> res) {
        if (n == null) return;
        if (isLeaf(n)) {
            res.add(n.val);
            return;
        }
        addLeaves(n.left, res);
        addLeaves(n.right, res);
    }
}

2Optimal (one DFS with boundary flags)

TimeO(n)Each node is visited exactly once.
SpaceO(h)Only the recursion stack, as deep as the tree height h.

Do a single preorder DFS where each call carries two flags: is this node on the left boundary, and is it on the right boundary. Leaves are added when reached. Left-boundary nodes are added before their children (top-down order), right-boundary nodes after their children (bottom-up order). A child inherits the left flag if it is the left child, or the right child when no left child exists; the right flag mirrors this.

  1. Add the root; if it is a leaf, return.
  2. dfs(root.left, left = true, right = false) and dfs(root.right, left = false, right = true).
  3. In dfs: if the node is a leaf, add it and return. If left, add it now.
  4. Recurse: left child gets (left, right && node.right == null); right child gets (left && node.left == null, right).
  5. After both recursive calls, if right, add the node.
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        res.add(root.val);
        if (root.left == null && root.right == null) return res;
        dfs(root.left, true, false, res);
        dfs(root.right, false, true, res);
        return res;
    }

    private void dfs(TreeNode n, boolean left, boolean right, List<Integer> res) {
        if (n == null) return;
        if (n.left == null && n.right == null) {
            res.add(n.val);
            return;
        }
        if (left) res.add(n.val);
        dfs(n.left, left, right && n.right == null, res);
        dfs(n.right, left && n.left == null, right, res);
        if (right) res.add(n.val);
    }
}

Edge cases to test

  • Single node
  • Root without a left child (empty left boundary) or without a right child (empty right boundary)
  • A left boundary that has to step right because a node has no left child
  • Skewed trees, where the boundary includes almost every node

Hints

Hint 1

Split the answer into four parts: the root, the left boundary without leaves, all leaves left to right, and the right boundary without leaves in reverse.

Hint 2

Walking the left boundary: from a node go left if possible, otherwise go right; stop before a leaf. The right boundary mirrors this.

Hint 3

One preorder DFS can do it all if each call knows whether the node is on the left boundary or on the right boundary. Add right-boundary nodes after visiting their children to get bottom-up order.

FAQ

What is the best time complexity for Boundary of Binary Tree?

Optimal (one DFS with boundary flags) runs in O(n) time and O(h) extra space. Each node is visited exactly once.

Which pattern does Boundary of Binary Tree use?

It is a trees & bst problem that uses the views pattern. Other problems with the same pattern: Top View of Binary Tree, Bottom View of Binary Tree, Left View of Binary Tree.

Is there a brute force solution for Boundary of Binary Tree?

Yes. Three separate walks takes O(n) time and O(n) space. Build the answer piece by piece: the root, then walk down the left edge (preferring left children) adding non-leaves, then add every leaf with a DFS, then walk down the right edge (preferring right children) collecting non-leaves and append them in reverse.

Which edge cases should I test for Boundary of Binary Tree?

Single node; Root without a left child (empty left boundary) or without a right child (empty right boundary); A left boundary that has to step right because a node has no left child; Skewed trees, where the boundary includes almost every node.