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:

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: