Boundary Traversal of Binary tree
The boundary traversal of the binary tree consists of the left boundary, leaves, and right boundary without duplicate nodes as the nodes may contain duplicate values. There are two types of boundary, i.e., left boundary and right boundary. The left boundary can be defined as the path from the root to the left-most node, whereas the right boundary can be defined as the path from the root to the right-most node. If the root node does not contain any left and right subtree, then the root node itself would be considered as the left boundary and right boundary.
Let’s understand the boundary traversal of binary tree through an example.
Consider the below tree:
We have to perform a boundary traversal in the above binary tree. First, we traverse all the nodes that appear on the left in the above binary tree that comes under the boundary traversal. The nodes that appear on the left are a b c d f e. The nodes that appear on the right are a k l n. We have traversed the left and right nodes, and now we will traverse the leaf nodes. In the above tree, the leaf nodes are e g h j m n. Some of the nodes repeated in all the boundaries; for example, node ‘a’ appears in both left and right boundary, so we will remove ‘a’ from the right boundary, and now it appears only once. Some of the nodes are also repeated in leaf nodes. Since node ‘e’ appears in both left boundary and leaf node so we will remove ‘e’ from the leaf node. The node ‘n’ also appears in both right boundary and leaf node, so we will remove the node ‘n’ from the leaf node. Therefore, the final boundary traversal of tree would be:
a b c d f e k l n g h j
Suppose we want to perform boundary binary tree traversal in an anti-clockwise direction, then the problem is broken down into four parts:
- First root would be printed.
- The leftmost nodes except the leaf nodes would be traversed.
- Leaf nodes
- The rightmost nodes except the leaf nodes would be traversed.
Source code to find leftmost nodes in a binary tree given below:
Source code to find rightmost nodes in a binary tree given below:
Source code to print the leaf nodes.
Below is the C implementation for the boundary traversal of a binary tree