# To print the boundary of Binary Tree

algorithmbinary-search-treebinary-treegraph-algorithmtree

I have been asked in an interviews to print the boundary of the Binary Tree. For example.

``````      1
/    \
2      3
/  \   /  \
4    5 6    7
/   \     \
8     9     10
``````

Answer will be : 1, 2, 4, 8, 9, 10, 7, 3

I have given the following answer.

First Method :

I have used a Bool variable to solve the above problem.

``````void printLeftEdges(BinaryTree *p, bool print) {
if (!p) return;
if (print || (!p->left && !p->right))
cout << p->data << " ";
printLeftEdges(p->left, print);
printLeftEdges(p->right, false);
}

void printRightEdges(BinaryTree *p, bool print) {
if (!p) return;
printRightEdges(p->left, false);
printRightEdges(p->right, print);
if (print || (!p->left && !p->right))
cout << p->data << " ";
}

void printOuterEdges(BinaryTree *root) {
if (!root) return;
cout << root->data << " ";
printLeftEdges(root->left, true);
printRightEdges(root->right, true);
}
``````

His Response : You have used Bool variable so many times. Can you solve this without using that.

Second Method :

I simply used tree traversal to solve this problem.

``````1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts:
2.1 Print all leaf nodes of left sub-tree from left to right.
2.2 Print all leaf nodes of right subtree from left to right.
3. Print the right boundary in bottom-up manner.
``````

His Response : He was not happy with this method too. He told that you are traversing the tree 3 times. That is too much. Give another solution if you have any.

Third Method :
This time i have went for Level Order traversal (BFS).

`````` 1: Print starting and ending node of each level
2: For each other node check if its both the children are <b>NULL</b> then print that node too.
``````

His Response : He was not seems happy with this method too because this method takes extra memory of order O(n).

My question is that Tell me a method which traverse tree single times, do not use any Bool variable and do not use any extra memory. Is it possible?

#### Best Solution

I guess this should do the trick:

``````traverse(BinaryTree *root)
{
if (!root) return;
cout << p->data << " ";
if (root->left ) traverseL(root->left ); //special function for outer left
if (root->right) traverseR(root->right); //special function for outer right
}

traverseL(BinaryTree *p)
{
cout << p->data << " ";
if (root->left ) traverseL(root->left ); //still in outer left
if (root->right) traverseC(root->right);
}

traverseR(BinaryTree *p)
{
if (root->left ) traverseC(root->left );
if (root->right) traverseR(root->right); //still in outer right
cout << p->data << " ";
}

traverseC(BinaryTree *p)
{
if (!root->left && !root->right) //bottom reached
cout << p->data << " ";
else
{
if (root->left ) traverseC(root->left );
if (root->right) traverseC(root->right);
}
}
``````

Start with the `traverse` function. Got rid of the null-queries at the beginning of each method (avoids one function call at each end). Does not need bool variables, simply uses three different traversal methods:

• one for the left edge, outputting the node before traversal
• one for the right edge, outputting the node after traversal
• one for all other nodes, outputting the node if there are no siblings.