deepSWE.io

Boundary of Binary Tree

Trees

Problem Statement

The **boundary of a binary tree** is the concatenation of the **left boundary**, the **leaves**, and the **right boundary** without duplicate nodes.

The **left boundary** is the path from the `root` to the left-most node.
The **right boundary** is the path from the `root` to the right-most node.
The **leaves** are nodes with no children.

Example 1

Output: [1, 3, 4, 2]

Example 2

Output: [1, 2, 4, 7, 8, 9, 10, 6, 3]

Algorithm Explanation

The problem asks for the boundary of a binary tree, which consists of the left boundary, the leaves, and the right boundary. We can solve this by breaking it down into these three distinct parts.

Algorithm Steps

Root: Add the root node's value to our result list. This is always the first part of the boundary unless the root is a leaf.
Left Boundary: Traverse from the root's left child. At each node, add its value and move to the left child. If there's no left child, move to the right child. Stop when a leaf is reached.
Leaves: Perform a traversal (like DFS) on the entire tree. If a node has no left and no right child, it's a leaf. Add its value to the result.
Right Boundary: Traverse from the root's right child, but in reverse. This is best done with recursion. Traverse down, and add the node's value on the way back up. At each node, prefer the right child, otherwise take the left.

Start

Adding root node 1.

Result: [1]

Boundary of Binary Tree Solution


class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        if not root.left and not root.right:
            return [root.val]

        result = [root.val]
        
        # Left Boundary
        curr = root.left
        while curr:
            if curr.left or curr.right:
                result.append(curr.val)
            if curr.left:
                curr = curr.left
            else:
                curr = curr.right
        
        # Leaves
        def get_leaves(node):
            if not node:
                return
            if not node.left and not node.right:
                result.append(node.val)
            get_leaves(node.left)
            get_leaves(node.right)
        
        get_leaves(root)

        # Right Boundary
        right_boundary = []
        curr = root.right
        while curr:
            if curr.left or curr.right:
                right_boundary.append(curr.val)
            if curr.right:
                curr = curr.right
            else:
                curr = curr.left
        
        result.extend(right_boundary[::-1])
        
        # Remove duplicates
        seen = set()
        final_result = []
        for val in result:
            if val not in seen:
                final_result.append(val)
                seen.add(val)
        
        return final_result