Given a complete binary tree, you need find a node at which the next node need to be inserted, in the least time complexity.
Each node in binary tree is contains left, right and value only.
5
/. \
4 8
/
3
the next node is going to be insert in right side of 4.
I've given a solution that takes O(n) time [ BFS- Level order traversal ] with O(n) space complexity.
But he is insting me to done in O(logn) time.
Obeservation:
In complete binary tree, the node either added after the last level [when its full BT] or at the last level[when its not full BT].
We can find the height of binary tree in O(logn) time, hence the level.
We need to somehow discard half of the tree in processing everytime in order to get O(logn)