Problem statement

https://binarysearch.com/problems/Convert-to-Full-Binary-Tree/

Solution

Problem statement is not clear at all. What we need to do is if some node have only one children, reattach this node to its parent, it is not said in the problem statement! After we get it, solution is pretty easy: if we have leaf or None node, return it as it is. If we have only right children, we need to delete it, so return answer for left subtree. Similar for the left children. If we have both, run for both of them and attach to root.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        if not root or (not root.left and not root.right):
            return root
        if not root.left: return self.solve(root.right)
        if not root.right: return self.solve(root.left)

        root.left = self.solve(root.left)
        root.right = self.solve(root.right)
        return root