LinkedIn Interview Question

Traverse a binary there so that the order returned is ordered from smallest to greatest.

Interview Answers

Anonymous

Nov 6, 2013

each popping takes logn. hence O(ologn)

5

Anonymous

Feb 25, 2013

void inorder (Node * root){ if (root) { inorder(root->left) coutvalue; inorder(root->right) } }

2

Anonymous

Mar 19, 2013

This is a binary tree, not a binary search tree. Thus, in order traversal may not work.

Anonymous

Oct 16, 2013

If it isn't a binary search tree, then just traverse the tree in any which way and put the elements into a min heap. Then iteratively pop the min off the top to return smallest to greatest. Traversal would take O(n), building the min heap is also O(n), and popping min off n times is also O(n) so total is O(n).

1

Anonymous

Sep 21, 2012

In order binary tree traversal

1