We shall solve boundary traversal of binary tree in this tutorial.
Problem Statement:
Given a binary tree, list all the nodes that come in the boundary.
Consider the tree as below:
So the boundary traversal will be as below:
a b d h c g l i j f k
So how did we arrive at this solution?
To get the boundary traversal we need to list down these 3 nodes.
1. Left Boundary nodes
2. Right Boundary nodes
3. Leaf Nodes
First we shall list our left boundary as highlighted:
a, b, d, h
List out the right boundary as highlighted:
a, c, g, l
Next, list out all the leaf nodes as highlighted:
H, i, j, f, k, l
Now combine all the nodes:
a, b, d, h, a, c, g, l, h, i, j, f, k, l
As you can see that there are multiple nodes with the same names. Remove the nodes with same name to arrive at the result.
a, b, d, h, c, g, l, i, j, f, k