Google | Phone | Print BST leaves in alternate order
Anonymous User
2830
TreeGooglePhone ScreeningInterview

Question:
Given a BST. Print leaf nodes of the tree in following order: 1st, nth, 2nd, (n-1)th, 3rd,........

Example:

Input:
	   5
	 /   \
	3     8
   / \   / \
  1   4 6   9

Outut: 1, 9, 4, 6

My solution :
I used DFS traversal to store all leaf nodes in an array and then print leaf nodes in expected order in a for loop over array.

I was given feedback that I could solve it with better complexity. Can anyone suggest solution with better complexity?

Comments (10)