CODEWITHSUNDEEP
pythonpython-3.xalgorithmbinary-tree
hopelessmixa
hopelessmixa

Reputation: 15

An algorithm that determines the minimum leaf depth and the number of leaves in that depth

I need to make the algorithm that I indicated in the title, but I have a problem with the fact that I don’t know how to make it write out the number of leafs

My code:

class Node:
    def __init__(self , key):
        self.data = key
        self.left = None
        self.right = None
 
def minDepth(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    if root.left is None:
        return minDepth(root.right)+1
    if root.right is None:
        return minDepth(root.left) +1
     
    return min(minDepth(root.left), minDepth(root.right))+1
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print (minDepth(root))

So I would like to ask if anyone knows how to find the number of leafs at certain depth

Upvotes: 0

Views: 102

Answers (1)

kcsquared
kcsquared

Reputation: 5409

After finding the minimum depth using your current DFS algorithm, you can perform another DFS search, except you pass along as parameters the 'desired depth' and 'current depth'.

def count_leaves_at_depth(root, desired_depth, current_depth):
    if root is None or current_depth > desired_depth:
        return 0
    
    if root.left is None and root.right is None:
        return 1 if current_depth == desired_depth else 0
    
    if root.left is None:
        return count_leaves_at_depth(root=root.right,
                                     desired_depth=desired_depth,
                                     current_depth=current_depth + 1)
    
    if root.right is None:
        return count_leaves_at_depth(root=root.left,
                                     desired_depth=desired_depth,
                                     current_depth=current_depth + 1)

    return (count_leaves_at_depth(root=root.right,
                                  desired_depth=desired_depth,
                                  current_depth=current_depth + 1)
            + count_leaves_at_depth(root=root.left,
                                    desired_depth=desired_depth,
                                    current_depth=current_depth + 1))

print(count_leaves_at_depth(root=root,
                            desired_depth=minDepth(root),
                            current_depth=1))

Upvotes: 1

Related Questions