Given a complete Binary Tree, We need to insert a given value in Complete Binary Tree and at the same time all the properties of Complete Binary Tree should be maintained.

I gave a level order traversal solution which was O(n) Time, but he wanted more optimised. So I tried to make a dfs solution such that each time either we discard a left subtree or right subtree by checking which one is not full binary tree.
I proposed some solution after struggling alot. I told him my solution this way will give O(logn) Time. I got a rejection, but I am still struggling to find a correct solution for this problem. Any help will be highly appreciated.

My 3rd rejection from faamgs in a row :( It is really demotivating.