print boundary of binary tree

Question

How to print the outside frame of a binary tree.

1. the order is top to down, left to right, then down to top
2. print all leftest node and rightest nodes
3. print all leaf nodes

4. print all nodes which only have 1 leaf

            100
           /   \ 
         50     150
        / \      /
      24   57   130
     /  \    \    \
   12   30    60   132
   

e.g: the output should be 100, 50, 24, 12, 30, 57, 60, 130, 132, 150

If we write three different functions to print left nodes, leaf nodes and right nodes, it can be easily solved but it takes O(n+2logn) time.

I am also looking for an O(n) approach but condition is that each node should be visited only once, dont want this extra O(2logn) part.

Answer 1

This can be done in O(n) .That is ,we visit each node of the tree only once. Logic is as follows Maintain two variables left and right and initialize them to zero. When ever there is recursive call to left side increment left by 1 When ever there is recursive call to ride side increment right by 1

Starting from root,do inorder traversal and check whether right is zero, that means we never made recursive call to right. If yes print node, this means we are printing all leftmost nodes of tree .If right is non zero , they are not considered as boundaries,so look for leaf nodes and print them .

In the Inorder traversal after left sub tree calls are done you bubble up to root and then we do recursive call for right sub tree. Now check for leaves nodes first and print them ,then check whether left is zero, that means we made recursive call to left ,so they are not considered as boundary. If left is zero print node, this means we are printing all rightmost nodes of tree .

The code snippet is

void btree::cirn(struct node * root,int left,int right)
{



 if(root == NULL)
    return;
if(root)
{

    if(right==0)
    {

        cout<<root->key_value<<endl;
    }

     cirn(root->left,left+1,right);




if(root->left==NULL && root->right==NULL && right>0)
    {

            cout<<root->key_value<<endl;
    }





  cirn(root->right,left,right+1);
  if(left==0)
   {

       if(right!=0)
      {
            cout<<root->key_value<<endl;
       }


   }




}

}

Answer 2

Algo:

1. print the left boundary
2. print the leaves
3. print the right boundary

---

void getBoundaryTraversal(TreeNode t) {
        System.out.println(t.t);
        traverseLeftBoundary(t.left);
        traverseLeafs(t);
        //traverseLeafs(t.right);
        traverseRightBoundary(t.right);
    }
    private void traverseLeafs(TreeNode t) {
        if (t == null) {
            return;
        }
        if (t.left == null && t.right == null) {
            System.out.println(t.t);
            return;
        }
        traverseLeafs(t.left);
        traverseLeafs(t.right);
    }
    private void traverseLeftBoundary(TreeNode t) {
        if (t != null) {
            if (t.left != null) {
                System.out.println(t.t);
                traverseLeftBoundary(t.left);
            } else if (t.right != null) {
                System.out.println(t.t);
                traverseLeftBoundary(t.right);
            }
        }
    }

    private void traverseRightBoundary(TreeNode t) {
        if (t != null) {
            if (t.right != null) {
                traverseRightBoundary(t.right);
                System.out.println(t.t);
            } else if (t.left != null) {
                traverseLeafs(t.left);
                System.out.println(t.t);
            }
        }
    }

---

TreeNode definition:

class TreeNode<T> {

    private T t;
    private TreeNode<T> left;
    private TreeNode<T> right;

    private TreeNode(T t) {
        this.t = t;
    }
}