Boundary of Binary Tree

The problem can be tackled by breaking it into multiple tasks: collecting the left boundary, collecting the right boundary, and collecting the leaf nodes.

Left Boundary:
- Start from the root and traverse the left child if available, else traverse the right child (only if no left child).
- Continue this traversal till you reach a leaf node.
Right Boundary:
- Start from the root and traverse the right child if available, else traverse the left child (only if no right child).
- Continue this traversal till you reach a leaf node.
- It’s important to note that the right boundary will be collected in reverse order.
Leaves:
- Use Depth First Search (DFS) to traverse the tree and collect all leaf nodes.

Implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        # If the root is the only node in the tree
        if not root.left and not root.right:
            return [root.val]

        # Initializing the result with root value
        boundary = [root.val]

        # Helper function to get left boundary excluding the leaf node
        def getLeftBoundary(node):
            while node:
                # Break if it's a leaf node
                if not node.left and not node.right:
                    break
                boundary.append(node.val)
                if node.left:
                    node = node.left
                else:
                    node = node.right

        # Helper function to get the leaf nodes
        def getLeaves(node):
            if not node:
                return
            if not node.left and not node.right:
                boundary.append(node.val)
                return
            getLeaves(node.left)
            getLeaves(node.right)

        # Helper function to get right boundary excluding the leaf node
        def getRightBoundary(node):
            stack = []
            while node:
                # Break if it's a leaf node
                if not node.left and not node.right:
                    break
                stack.append(node.val)
                if node.right:
                    node = node.right
                else:
                    node = node.left
            while stack:
                boundary.append(stack.pop())

        # We skip the root for left and right boundary because it's already added.
        getLeftBoundary(root.left)
        getLeaves(root)
        getRightBoundary(root.right)

        return boundary

This solution covers the boundary of the binary tree by separately handling the left boundary, right boundary, and leaf nodes.