Question

Write a python function that takes a binary tree as its only parameter. Return the value stored in the shallowest leaf, anywhere in the tree. If there is a tie, then return the "leftmost" of the leaves (that is, the one that you would encounter first in an in-order traversal). You are allowed (and encouraged) to use a helper function. You may assume that the tree nodes have public fields left,right. The code cannot import anything from the Python standard library.

Answer 1

# We need to find the leaf which is leftmost and at the maximum depth.
def find_shallowest_left(node):
    
    queue = []
    queue.append(node)
    
    # are using BFS to traverse level by level,,
    # At the last level, the first entry will be our result
    while len(queue) != 0:
        nextLevelQueue = []
        currentLevel = queue[:]
        
        while len(queue) != 0:
            q = queue.pop(0)
            if q.left:
                nextLevelQueue.append(q.left)
            if q.right:
                nextLevelQueue.append(q.right)
                
        if len(nextLevelQueue) == 0:
            # It means we were processing the last level
            # Return the first element from last level then.
            return currentLevel[0].val
            
        else:
            queue = nextLevelQueue

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.