Binary Tree Doubt

Question

( Its a doubt so dont mark it as duplicate )

 

https://gateoverflow.in/1776/gate2014-1-12?show=27673#a27673

In the above answer, if I ignored all the ancestors of current node with subtree node count exact 4 as they surely will not have exact 4 count. ( they will have count more than 4 )

So ignoring such ancestors , can I reduce the time complexity ? or it will still be O(n) only ?

Please explain.

 

Question : 

 

Comments

Still in worst case you will take O(n) time itself to find such subtree.

---

@2019_Aspirant

Can you explain why it happens ?

---

Take any skew tree.  There you will have to go till $n-4$ at best & you will get $1$ count.  So it eventually took $O(n)$ time..