pythonalgorithmnested-if

Python nested if vs and behviour


I was solving the bottom view of a binary tree question using Python. This code is working.

class Solution:
    
    #Function to return a list of nodes visible from the top view 
    #from left to right in Binary Tree.
    def bottomView(self,root):
        dic = {}  
        result = []
        self.helper(root, dic, 0, 0)
        for i in sorted(dic.keys()):
            result.append(dic[i][0])
        return result
                
    def helper(self, root, d, hd, level):
        if root is None:
            return
       
        if hd in d:
            if level >= d[hd][1]:
                d[hd] = (root.data, level)
        else:
            d[hd] = (root.data, level)
             
        self.helper(root.left, d, hd - 1,level + 1)
        self.helper(root.right, d, hd + 1,level + 1)

Now, I have a doubt regarding this block of code:

if hd in d:
    if level >= d[hd][1]:
        d[hd] = (root.data, level)

If I replace it with this code:

if hd in d and level >= d[hd][1]:
    d[hd] = (root.data, level)

It does not work. As far as I understand the functionality of nested if block, the inner loop condition will be evaluated only if the outer loop condition evaluates to True which is similar to what is happening in the and statement. But the previous block gives me the correct output while the second block of code just does not work. Why is it so?

Link to problem statement :- https://practice.geeksforgeeks.org/problems/bottom-view-of-binary-tree/1


Solution

  • The problem is the else Block underneath!

    if hd in d:
        if level >= d[hd][1]:
            d[hd] = (root.data, level)
    else:
        d[hd] = (root.data, level)  # only when hd not there yet!
    

    is different from:

    if hd in d and level >= d[hd][1]:
        d[hd] = (root.data, level)
    else:
        d[hd] = (root.data, level)   # also when value for hd meets condition
    

    In the first, the else is executed when hd in d is not met.
    In the second, it is executed more often! Namely when the stronger hd in d and level >= d[hd][1] is not met. Take a close look at the second one: if and else execute the exact same code. That has to be pointless!

    If, in fact, you wanted to save some lines here, you could do:

    if hd not in d or level >= d[hd][1]:
        d[hd] = (root.data, level)