Boundary Of Binary Tree - Leetcode Solution

The problem "Boundary of Binary Tree" on LeetCode asks us to find and return the boundary of a binary tree in anti-clockwise direction starting from root.

We can solve this problem using a combination of three sub-problems:

1. Finding the left boundary of the binary tree
2. Finding the right boundary of the binary tree
3. Finding the leaf nodes of the binary tree

We will create three helper functions for these sub-problems and call them in the main function to get the final solution.

1. Finding the left boundary of the binary tree: We can find the left boundary of the binary tree by traversing the root node, then traversing all the left nodes until we reach a leaf node. At each node, we check if it has a left child. If it has a left child, we move to that child and add the current node value to the result list. If it doesn't have a left child, we move to the right child and continue the traversal.

2. Finding the right boundary of the binary tree: We can find the right boundary of the binary tree by traversing the root node, then traversing all the right nodes until we reach the leaf node. At each node, we check if it has a right child. If it has a right child, we move to that child and add the current node value to the result list. If it doesn't have a right child, we move to the left child and continue the traversal.

3. Finding the leaf nodes of the binary tree: We can find the leaf nodes of the binary tree using depth-first search. We traverse the left child, then the right child until we reach a leaf node. We add the leaf node's value to the result list.

Now, we can combine these three functions to get the final solution. We add the root node's value to the result list, then call the three sub-problems in the following order:

1. Find the left boundary of the binary tree, starting from the root's left child.
2. Find the leaf nodes of the binary tree.
3. Find the right boundary of the binary tree, starting from the root's right child in reverse order.

Finally, we concatenate these three lists and return the result.

Here is the Python implementation of the solution:

class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        res = [root.val]
        self.leftBoundary(root.left, res)
        self.leaves(root, res)
        self.rightBoundary(root.right, res)
        
        return res
    
    def leftBoundary(self, node, res):
        if not node or (not node.left and not node.right):
            return
        
        res.append(node.val)
        if node.left:
            self.leftBoundary(node.left, res)
        else:
            self.leftBoundary(node.right, res)
    
    def rightBoundary(self, node, res):
        if not node or (not node.left and not node.right):
            return
        
        if node.right:
            self.rightBoundary(node.right, res)
        else:
            self.rightBoundary(node.left, res)
        res.append(node.val)

    def leaves(self, node, res):
        if not node:
            return
        
        if not node.left and not node.right:
            res.append(node.val)
            return
        
        self.leaves(node.left, res)
        self.leaves(node.right, res)

Overall, the time complexity of this solution is O(n) where n is the number of nodes in the binary tree as we traverse every node once. The space complexity is also O(n) in the worst-case scenario when the tree is completely unbalanced and resembles a linked list.

1