Boundary of Binary Tree

Description

Let’s start by defining what a boundary of a binary tree is. We can define it as:

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary. Take a look at the example given below:

Take a look at the example given below:

As mentioned above, the boundary can be divided into four categories; the following explains these categories:

• Root node

• Left boundary

  • The root node’s left child is in the left boundary. If the root does not have a left child, the left boundary is empty.
  • If a node in the left boundary has a left child, the left child is in the left boundary.
  • If a node in the left boundary has a right child but no left child, the right child is in the left boundary.
  • The leftmost leaf is not in the left boundary.

• Right boundary

  • The right boundary is similar to the left boundary, except it is on the right side of the root's right subtree.
  • The leaf is not part of the right boundary.
  • The right boundary is empty if the root does not have a right child.

• Leaves

  • The leaves are nodes that do not have any children. For this problem, we can assume that the root is not a leaf.