545. Boundary of Binary Tree - Explanation

Description

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary.

The left boundary is the set of nodes defined by the following:

The root node's left child is in the left boundary. If the root does not have a left child, then the left boundary is empty.
If a node is in the left boundary and has a left child, then the left child is in the left boundary.
If a node is in the left boundary, has no left child, but has a right child, then the right child is in the left boundary.
The leftmost leaf is not in the left boundary.

The right boundary is similar to the left boundary, except it is the right side of the root's right subtree. Again, the leaf is not part of the right boundary, and the right boundary is empty if the root does not have a right child.

The leaves are nodes that do not have any children. For this problem, the root is not a leaf.

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

Example 1:

Input: root = [1,null,2,3,4]

Output: [1,3,4,2]

Explanation:

The left boundary is empty because the root does not have a left child.
The right boundary follows the path starting from the root's right child 2 -> 4.
4 is a leaf, so the right boundary is [2].
The leaves from left to right are [3,4].
Concatenating everything results in [1] + [] + [3,4] + [2] = [1,3,4,2].

Example 2:

Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]

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

Explanation:

The left boundary follows the path starting from the root's left child 2 -> 4.
4 is a leaf, so the left boundary is [2].
The right boundary follows the path starting from the root's right child 3 -> 6 -> 10.
10 is a leaf, so the right boundary is [3,6], and in reverse order is [6,3].
The leaves from left to right are [4,7,8,9,10].
Concatenating everything results in [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3].

Constraints:

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

Company Tags

1. Simple Solution

class Solution:
    def isLeaf(self, t: Optional[TreeNode]) -> bool:
        return t.left is None and t.right is None
    
    def addLeaves(self, res: List[int], root: Optional[TreeNode]) -> None:
        if self.isLeaf(root):
            res.append(root.val)
        else:
            if root.left is not None:
                self.addLeaves(res, root.left)
            if root.right is not None:
                self.addLeaves(res, root.right)
    
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if root is None:
            return res
        
        if not self.isLeaf(root):
            res.append(root.val)
        
        t = root.left
        while t is not None:
            if not self.isLeaf(t):
                res.append(t.val)
            if t.left is not None:
                t = t.left
            else:
                t = t.right
        
        self.addLeaves(res, root)
        
        stack = []
        t = root.right
        while t is not None:
            if not self.isLeaf(t):
                stack.append(t.val)
            if t.right is not None:
                t = t.right
            else:
                t = t.left
        
        while stack:
            res.append(stack.pop())
        
        return res

Time & Space Complexity

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

Where $n$ is the number of nodes in the tree

2. Using PreOrder Traversal

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))

Time & Space Complexity

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

Where $n$ is the number of nodes in the tree