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

The boundary is formed by concatenating the following four parts:

$1$. The root node itself (the root is never considered a leaf in this problem).

$2$. The left boundary: the path of non-leaf nodes starting from the root’s left child, always preferring the left child at each step, and falling back to the right child only when no left child exists. If the root has no left child, the left boundary is empty.

$3$. The leaves: all nodes with no children, ordered from left to right. The root is excluded even if it has no children.

$4$. The right boundary (in reverse order): the path of non-leaf nodes starting from the root’s right child, always preferring the right child at each step, and falling back to the left child only when no right child exists, collected in reverse (bottom to top). If the root has no right child, the right boundary is empty.

Note: A leaf node is any node with no left or right child. The root is never treated as a leaf for this problem. The leftmost and rightmost leaves are not included in the left or right boundaries respectively, only in the leaves section.

Constraints:

• $1 \leq$ number of nodes $\leq 10^4$

• $-1000 \leq$ Node.val $\leq 1000$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.