Understanding the Problem

A binary tree is given as root. It can go both left and right, or only left or only right. It is to return the minimum difference between the nodes. It should be an absolute number though.

As an example, if there is a tree tree = [4, 2, 6, 1, 3, None, None] it could be visualised as,

      4
     / \
    2   6
   / \
  1   3

The minimum absolute difference between nodes will be 1, it could be seen at the nodes of 2 and 1 from the bottom, or 2 and 3. The difference will be diff = abs(2 - 1), which is 1, or diff = abs(2 - 1), which is also 1. So it returns 1.

Approach

When I see a problem like a binary tree, I know I should think about the recursion solution. But the trick was, it was not that each node will have either two sides of left and right or None, but there was a possibility that a single node could have only one side(left or right), both sides or None. My assumption thinking that it will always have both sides and None was incorrect and blew out my precious time though.

It has got to be with a global variable and a recursion, but time passed too much I had a little help by AI.

Solution

A class TreeNode is given as,

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

I used prev and min_diff as variables to save values and defined a function within the method so I could solve the problem with recursion.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        prev = None
        min_diff = float("inf") # give as biggest value as possible

        def inner(rt):
            nonlocal prev, min_diff
            if not rt:
                return

            # check left side
            inner(rt.left)

            if prev != None:
                min_diff = min(abs(rt.val - prev), min_diff)

            prev = rt.val

            # check right side
            inner(rt.right)

        inner(root)
        return min_diff

1. min_diff is initialised with ”inf” so it could be the biggest number which will not be used in any case before doing some calculation

2. Check left side of the node first with inner(rt.left)

3. If there is a previous number, compare the min_diff and abs(rt.val - prev), then store it in the min_diff again so to be returned later

4. Store rt.val in prev to be used later in the next recursion

5. Check right side and it will do the same process as left

6. Return min_diff

Reflection

The binary tree problem has a simple solution and I could easily think about how I could solve it. But the problem is that it is only easy to think about the whole concept. When I go deeper in the process it is somewhat confusing, kind of lost somewhere when I have to initialise values and re-set values. The codes where they are supposed to be are not there and I need to take time to think about how the code will run.

It is true that I would need more practice to understand the recursion and binary tree problems. For now it may be hard to solve it, yet will it be easier in the sooner future for me to handle it, i believe.