Finding Shortest Path to Node with Given Value - Binary Tree

Question

Given a Binary Tree, I wanted to find the depth at which a specific value appears.

def find_depth_of_val(self, root, val):
    if not root:
        return 10000000
    if root.val == val:
        return 0
    return 1 + min(self.find_node(root.right, val), self.find_node(root.left, val))

This is the idea I had, you'll probably see a wild "return 10000000", which I used to make it so that if there is nothing else on a specific path, i.e. a leaf's next has been reached without finding the node we want, that the function knows the answer isn't there and doesn't return that possibility.

What I'm wondering is whether there's a better way to do this, one without using a random "return 10000000".

Edit: Someone gave me a solution in which I kind of change it to:

def find_depth_of_val(self, root, val):
    if not root:
        return None
    if root.val == val:
        return 0
    right_side = self.find_node(root.right, val)
    left_side = self.find_node(root.left, val)
    if right_side is None:
        return left_side
    elif left_side is None:
        return right_side
    else:
        return 1 + min(self.find_node(root.right, val), self.find_node(root.left, val))

In such a case like this, how should I type hint it considering we could be returning either None or an integer? That said, I'm still open to seeing if anyone else has any different solution designs!!

Why not use the float infinity there. You can obtain it with float('inf') or math.inf. — Lukas S
– Lukas S, Commented Oct 18, 2021 at 16:15

sevan · Accepted Answer · 2021-10-18 16:35:36Z

1

This looks weird that find_depth_of_val has both self (a tree) and root (another tree) as parameters. Besides when you state your problem you talk of only one tree and self is actually not used in your method.

So assuming your values in the tree are unique, here is a solution. The method returns None if no path is found or otherwise the depth. Optional[int] means either an int or either None:

def find_depth_of_val(self, val: int) -> Optional[int]:
    if self.val == val:
        return 0
    for node in (self.left, self.right):
        if node is not None:
            depth = node.find_depth_of_val(val)
            if depth is not None:
                return depth + 1
    return None

answered Oct 18, 2021 at 16:35

sevan

3,9743 gold badges19 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Finding Shortest Path to Node with Given Value - Binary Tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related