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.
Related Question