Boundary of Binary Tree

Medium · Graphs · Explanation and code example

Using PreOrder Traversal

How it works

We can collect all boundary nodes in a single preorder traversal by tracking where each node belongs. Using a flag system, we mark nodes as: root (0), left boundary (1), right boundary (2), or internal (3). During traversal, we determine each child's flag based on the parent's flag and whether siblings exist. Left boundary nodes go directly to the result, right boundary nodes are collected in reverse order, and leaves are gathered separately.

Steps

  1. Create three lists: left_boundary, right_boundary, and leaves.
  2. Perform a preorder traversal with a flag indicating the node's role:
    • If the node is on the right boundary (flag = 2), prepend its value to right_boundary.
    • If the node is on the left boundary or is the root (flag = 0 or 1), append its value to left_boundary.
    • If the node is a leaf and not already counted, append to leaves.
  3. For each child, calculate its flag:
    • Left child inherits left boundary status, or becomes right boundary if it is the only child of a right boundary node.
    • Right child inherits right boundary status, or becomes left boundary if it is the only child of a left boundary node.
  4. Concatenate left_boundary + leaves + right_boundary and return.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Where n is the number of nodes in the tree

Things to watch for

Including Leaves in the Left or Right Boundary

Leaf nodes should only appear once in the leaves section, not in the left or right boundary. Adding a leaf while traversing the left boundary causes duplicates in the result.

Incorrect Right Boundary Order

The right boundary must be added in bottom-to-top order. A common mistake is adding nodes directly to the result during traversal (top-to-bottom), instead of using a stack or reversing at the end.

Missing the Single-Child Case in Boundary Traversal

When traversing the left boundary, if a node has no left child, you must continue with the right child (and vice versa for the right boundary). Stopping traversal at missing children misses boundary nodes deeper in the tree.

Python code example

from typing import List, Optional

class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        left_boundary, right_boundary, leaves = [], [], []
        self.preorder(root, left_boundary, right_boundary, leaves, 0)
        left_boundary.extend(leaves)
        left_boundary.extend(right_boundary)
        return left_boundary

    def is_leaf(self, cur):
        return cur.left is None and cur.right is None

    def is_right_boundary(self, flag):
        return flag == 2

    def is_left_boundary(self, flag):
        return flag == 1

    def is_root(self, flag):
        return flag == 0

    def left_child_flag(self, cur, flag):
        if self.is_left_boundary(flag) or self.is_root(flag):
            return 1
        elif self.is_right_boundary(flag) and cur.right is None:
            return 2
        else:
            return 3

    def right_child_flag(self, cur, flag):
        if self.is_right_boundary(flag) or self.is_root(flag):
            return 2
        elif self.is_left_boundary(flag) and cur.left is None:
            return 1
        else:
            return 3

    def preorder(self, cur, left_boundary, right_boundary, leaves, flag):
        if cur is None:
            return

        if self.is_right_boundary(flag):
            right_boundary.insert(0, cur.val)
        elif self.is_left_boundary(flag) or self.is_root(flag):
            left_boundary.append(cur.val)
        elif self.is_leaf(cur):
            leaves.append(cur.val)

        self.preorder(cur.left, left_boundary, right_boundary, leaves, self.left_child_flag(cur, flag))
        self.preorder(cur.right, left_boundary, right_boundary, leaves, self.right_child_flag(cur, flag))

C++ code example

class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        vector<int> left_boundary, right_boundary, leaves;
        preorder(root, left_boundary, right_boundary, leaves, 0);
        left_boundary.insert(left_boundary.end(), leaves.begin(), leaves.end());
        left_boundary.insert(left_boundary.end(), right_boundary.begin(), right_boundary.end());
        return left_boundary;
    }

private:
    bool isLeaf(TreeNode* cur) {
        return cur->left == nullptr && cur->right == nullptr;
    }

    bool isRightBoundary(int flag) {
        return flag == 2;
    }

    bool isLeftBoundary(int flag) {
        return flag == 1;
    }

    bool isRoot(int flag) {
        return flag == 0;
    }

    int leftChildFlag(TreeNode* cur, int flag) {
        if (isLeftBoundary(flag) || isRoot(flag)) {
            return 1;
        } else if (isRightBoundary(flag) && cur->right == nullptr) {
            return 2;
        } else {
            return 3;
        }
    }

    int rightChildFlag(TreeNode* cur, int flag) {
        if (isRightBoundary(flag) || isRoot(flag)) {
            return 2;
        } else if (isLeftBoundary(flag) && cur->left == nullptr) {
            return 1;
        } else {
            return 3;
        }
    }

    void preorder(TreeNode* cur, vector<int>& left_boundary, vector<int>& right_boundary, vector<int>& leaves, int flag) {
        if (cur == nullptr) {
            return;
        }

        if (isRightBoundary(flag)) {
            right_boundary.insert(right_boundary.begin(), cur->val);
        } else if (isLeftBoundary(flag) || isRoot(flag)) {
            left_boundary.push_back(cur->val);
        } else if (isLeaf(cur)) {
            leaves.push_back(cur->val);
        }

        preorder(cur->left, left_boundary, right_boundary, leaves, leftChildFlag(cur, flag));
        preorder(cur->right, left_boundary, right_boundary, leaves, rightChildFlag(cur, flag));
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations