Print edge nodes (boundary) of a binary tree

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.

Assume we have a binary tree below:

      
    _30_
   /    \   
  10    20
 /     /  \
50    45  35

The correct solution should print 301050453520.

Another binary tree:

             _30______
       /              \
    __20__          __40__
   /      \        /      \
  10      25      35      50
 /  \       \            /
 5  15      28          41

The correct solution should print 3020105152835415040.

Further Thoughts:

Please note that the above problem statement does not give a clear definition of “left-most” node. Thanks to my dear readers who pointed out this ambiguity, which I didn’t consider earlier in my above solution.

For example, consider the binary tree below: Is node 8 a left-most node?

  
           ___28_______________
  /                                \
  4____                        ____69
       \                      /
      __8__                __56__
     /     \              /      \
   __7     12__        __34    __27__
  /            \      /       /      \
  5_          _13    _2      _3      39
    \        /      /       /
     6      11     10       9
The correct output is: 2848756, 1110939275669. 
C++:
01 void printEdgeLB(Node* head, map<int,int>& m, int level)
02 {
03     if(head==NULL)
04         return;
05     if(m.find(level)==m.end()){
06         m[level]=1;
07         cout<<head->value<<” “;
08     }else if((!(head->left))&&(!(head->right)))
09         cout<<head->value<<” “;
10     printEdgeLB(head->left,m,level+1);
11     printEdgeLB(head->right,m,level+1);
12 }
13 
14 void printEdgeR(Node* head, map<int,int>& m, int level)
15 {
16     if(head==NULL)
17         return;
18     printEdgeR(head->right,m,level+1);
19     printEdgeR(head->left,m,level+1);
20     if((!level)||(!head->left)&&(!head->right)){
21         m[level]=1;
22         return;
23     }
24     if(m.find(level)==m.end()){
25         m[level]=1;
26         cout<<head->value<<” “;
27     }
28 }
Advertisements
This entry was posted in Hashtable and Map, Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s