Programming Interview 45: Print a full binary tree's boundary in counterclockwise order

Step by step to crack Programming Interview question 45: Print a full binary tree's boundary in counterclockwise order
Please watch the video for example and demo.

Solution:
1. Print the left boundary
1.1. Similar to preorder, ONLY deal with left child!

2. Print all leaf nodes
2.1. Similar to inorder (or preorder), ONLY print leaf nodes!

3. Print the right boundary
3.1. Similar to a postorder, ONLY deal with right child!

[AI_Edu_]

I agree with you. But basically you can assume that's O(n) since O(n+2logn) = O(n)

[AI_Edu_]

The leaves and left/right most nodes, that's what I think.

[AI_Edu_]

Given the example in the slides, if you use preorder you will get 1, 2, 4, 5, 3, 6, 7. I guess your idea may not work.

[AI_Edu_]

No. 5, 6 are not leaves nor left/right most nodes so ignore.

[MrEugeneleo]

I have a question: why not use Preorder and Postorder to print the leaf, I think it doesn't matter whether you use which order since all of them will give you the same order. Is that true?

[prasad]

Hi,

I have a small doubt about function
inorderLeafOnly(){
if(this == null) return;
}
if the calling object was null then the function call would not have happened in the first place right ??
I feel that check is not necessary

[anura]

what is the time complexity of this solution? I think it will be O(n+2logn). Let me know your thoughts.

[iacar]

What happens if you have one more level in your test case? e.g. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. Would your code print 5 and 6?

[AI_Edu_]

It will print 8, 4, 2, 1, 2, 3, 5, 9, 11, 13, 15, 14, 12, 8. So 5 will be printed, 6 won't.

[amitshukla]

what will happen if root does not have right child but root's left child has right subtree?
In that case your code will not print right boundary. Please respond.

[MrEugeneleo]

this question actually is pretty tricky depend on the definition of "boundary ".