Tree Bounday Traversal

"""
Boundary traversal is done in anti-clockwise order: root -> left boundary -> all leaves -> right boundary.
Left and right boundary functions skip leaf nodes to avoid duplicates (leaves are collected separately).
We call left_tra(root.left) and right_tra(root.right) so root is not repeated.
Right boundary is added after recursion so it automatically comes in reverse order.
"""
def left_tra(root, ans):
    if root and (root.left or root.right): # skip leaf nodes
        ans.append(root.data)
        if root.left:
            left_tra(root.left, ans)
        else:
            left_tra(root.right, ans)

def leaves(root, ans):
    if not root:
        return
    if not root.left and not root.right: # leaf node
        ans.append(root.data)
        return

    leaves(root.left, ans)
    leaves(root.right, ans)


def right_tra(root, ans):
    if root and (root.left or root.right): # skip leaf nodes
        if root.right:
            right_tra(root.right, ans)
        else:
            right_tra(root.left, ans)
        ans.append(root.data) # add after recursion for reverse order


class Solution:
    def boundaryTraversal(self, root):
        if not root:
            return []
        ans = []
        if root.left or root.right: # add root only if not leaf
            ans.append(root.data)

        left_tra(root.left, ans) # left boundary
        leaves(root, ans) # all leaves
        right_tra(root.right, ans) # right boundary in reverse
        return ans