Right side view of BST - Python

Question

I am trying to find the right side view of a BST. I am able to get a working solution but I noticed a perculiatity with using

for i in q: vs for i in range(len(q))

To elaborate the below code works

 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    if root == None:
        return []

    result = []
    
    q = []
    q.append(root)
    
    while len(q):
        
        for _ in range(len(q)):
            node = q.pop(0)
            if node.left != None:
                q.append(node.left)
                
            if node.right != None:
                q.append(node.right)
        result.append(node.val)
        
    return result

but then when I change the below

for _ in range(len(q)):

to

for _ in (q):

as shown below

    if root == None:
        return []

    result = []
    
    q = []
    q.append(root)
    
    while len(q):
        
        for _ in (q):
            node = q.pop(0)
            if node.left != None:
                q.append(node.left)
                
            if node.right != None:
                q.append(node.right)
        result.append(node.val)
        
    return result

I know longer get the right side view. Anyone have any idea why this is the case.

For example with the input

Input: root = [1,2,3,null,5,null,4]

I get the output using the range(len(q)) code Output: [1,3,4]

but when I try using the range(q) code I get the output Output: [2,5,4]

user_17030540 · Answer

The problem is that you're modifying q while iterating over it by popping the first element off. The iterator than gets the element from the next position in the the list, but all of the elements have shifted left by 1 position.

In the first example, using range(len(q)), the results work out because the iterator was defined based on the length of q at the start of the loop, so if q had 4 elements, it will always loop for 4 iterations. _ in (0, 1, 2, 3)

In the second example, each time you call q.pop(0), it shifts the elements of the list left by one position, which causes it to skip every other element.

Example:

a = [ x for x in range(10)]
for val in a:
    print(val, a.pop(0))

# OUTPUT
 0 0
 2 1
 4 2
 6 3
 8 4

Note how val was only getting the even values, because the iterator created by the for loop is getting the next position in the list (0, 1, 2, 3, 4, etc), while the list itself is being shifted left on every iteration. This also means it only gets 5 values instead of 10 before hitting the StopIteration exception that ends the loop.

Right side view of BST - Python

1 Answers