LC: Boundary of Binary Tree - spiralgo/algorithms GitHub Wiki

Boundary of Binary Tree

The Essence:

As stated in the problem, an algorithm consisting of 3 procedures is required to solve this problem:

1. Get the Left Boundary of the Tree:

Here, we go as left as we can. If we encounter a node without left children, we go to its right and go as left as we can from there, until we hit the leaf with no roots, which is not considered to be part of the left boundary, belonging to the leaves group instead.

2. Get the Right Boundary of the Tree

We basically apply the same procedure as the left boundary one. We go right as much as we can and turn left if necessary, avoiding the right-most leaf at the end.

3. Get the Leaves of the Tree

For this, the tree must be traversed up the its leaves from left to right. The leaves can be checked by whether they have any children.

Details:

All procedures here can be implemented recursively with checks for the respective procedure.

The code can be found here: https://github.com/spiralgo/algorithms/blob/master/src/main/java/algorithms/curated170/medium/BoundaryOfBinaryTree.java