Hello! Today we’ll looking at how to delete even leaf nodes repeatedly. This means, after deleting a leaf even node, if the parent of the deleted node becomes an even leaf node, then it should be deleted too, repeatedly.
When I first saw this question, it was a little tricky. Deleting the even leaf nodes is quite simple but doing it repeatedly was something that I got confused with.
After some time, I tried my favorite technique that I created for problem-solving: “I don’t care how but just need to” method. This first sounds a bit ludicrous but it will make sense more later(This method was helpful for dynamic programming to me)
So, our goal is to delete even leaf nodes repeatedly. I formulated the code as what the question is literally asking. I don’t care how but I just want to delete even leaf node.
But since we have to do it repeatedly,
When a node’s left or right child 1)exists, 2)leaf node 3)has even value, then discard the child and make it nullptr.
The above code works, but I was inspired by K_Ayush to make a more clear and concise version. This is the bottom up approach. Instead of focusing on the parent node, we determine what we return. If the current node is an even leaf node, then return null, otherwise, return the original node. Below is the code.
Time Complexity: O(n)
