To print the boundary of Binary Tree

Question

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?

Answer 1

Below is a recursive solution in Python3 with time complexity O(n). Algorithm here is to print left most nodes from top to bottom, leaf nodes from left to right and right most nodes from bottom to top. Adding boolean flags (isLeft,isRight) for left and right tree traversal simplifies the code and drives the time complexity of O(n).

#Print tree boundary nodes
def TreeBoundry(node,isLeft,isRight):
    #Left most node and leaf nodes
    if(isLeft or isLeaf(node)): print(node.data,end=' ')
    #Process next left node
    if(node.getLeft() is not None): TreeBoundry(node.getLeft(), True,False)
    #Process next right node
    if(node.getRight() is not None):TreeBoundry(node.getRight(), False,True)
    #Right most node
    if(isRight and not isLeft and  not isLeaf(node)):print(node.data,end=' ')

#Check is a node is leaf
def isLeaf(node):
   if (node.getLeft() is None and  node.getRight() is None):
       return True
   else:
       return False

#Get started
#https://github.com/harishvc/challenges/blob/master/binary-tree-edge-nodes.py
TreeBoundry(root,True,True)