Given a binary tree (not BST), we are supposed to find nth smallest element?

Question

How to find the smallest element in a Binary Tree (Not BST)? Sample C/C++ code would be helpful.

Answer 1

Algorithm to find nth smallest element in Binary Tree(Not BST)

1. Take dynamic Array(in c++/java)
2. Traverse all the elements of The given Binary Tree using any traversal algorithm (inorder, preorder, postorder, levelorder method) and keep each element in dynamic array.
3. Sort dynamic Array in non decreasing order.
4. choose nth element in Array i.e Array[n].

Time complexity=O(n)+O(nlogn)+O(1)=O(nlogn).

Comments

What is levelorder traversal?