1

I am trying to find the total depth of a BST in python(such that the root is at depth 1, its children depth 2, those children depth 3 etc) and the total is all of those depths added together. Ive been trying for about 5 hours straight now and cannot figure it out. Here is the code I have produced so far 

class BinaryTreeVertex:
    '''vertex controls for the BST'''

    def __init__(self, value):
        self.right = None 
        self.left = None
        self.value = value

    ...

    def total_Depth(self):
        print ("val:", self.value)
        if self.left and self.right:
            return (self.left.total_Depth()) + 1 and (self.right.total_Depth()) + 1
        elif self.left:
            return 1 + self.left.total_Depth()
        elif self.right:
            return 1 + self.right.total_Depth()
        else:
            return 1
...

tree = BinarySearchTree()     
arr = [6,10,20,8,3]
for i in arr:
    tree.insert(i)
tree.searchPath(20)
print (tree.total_Depth()) #this calls the total_depth from vertex class

The generated tree then looks like this.

   6         # Depth 1
___|___
3     10     # Depth 2
    ___|__
    8    20  # Depth 3

But when I run it it prints:

val: 6
val: 3
val: 10
val: 8
val: 20
3

The 3 should actually be an 11 with this tree but I cannot figure out how to get it. Please help

edit: To clarify, i am NOT looking for the max depth, I know how to find this. I need the total depth the way i explained, where the depth is the level of the tree. it would be 11 here as 6 would have depth 1, 3 and 10 depth 2, and 8 and 20 depth 3, where 1+2+2+3+3=11. I need it for a ratio regarding run times

Improve this question
8
  • 1
    what are you trying to accomplish doing return (self.left.total_Depth()) + 1 and (self.right.total_Depth()) + 1? This is always going to return the depth of the right branch plus one. You probably want max((self.left.total_Depth()) + 1, (self.right.total_Depth()) + 1) Commented Feb 24, 2018 at 2:11
  • 1
    How did you figure out your desired return value is 11? I think you are confusing tree values and tree depth, which are completely separate things. Do you want the depth of the tree or a sum of the values traversed along a path? Commented Feb 24, 2018 at 2:21
  • github.com/joowani/binarytree Commented Feb 24, 2018 at 4:16
  • I very much doubt you want to sum the depths at each levels (and in any case that total would just be D(D+1)/2 ). Presumably you only want to find max depth. Commented Feb 24, 2018 at 9:06
  • In any case your bug is expr1 and expr2. Olivier's answer shows the clean way of implementing your depth function in three lines. Commented Feb 24, 2018 at 9:09

1 Answer 1

Reset to default
1

You problem comes from this line.

return (self.left.total_Depth()) + 1 and (self.right.total_Depth()) + 1

Using and will return the leftmost falsy value provided, or rightmost if they are all truthy. In that case, it actually ends up always returning self.right.total_Depth() + 1.

What I recommend is keeping track of the nodes depth through a keyword argument, I called it _depth to emphasize that it should be private, i.e. not provided by the user.

class BinaryTreeVertex:

    ...

    def total_depth(self, _depth=1):

        if self.left and self.right:
            return self.left.total_depth(_depth=_depth + 1) \
                   + self.right.total_depth(_depth=_depth + 1) \
                   + _depth

        elif self.left:
            return _depth + self.left.total_depth(_depth=_depth + 1)

        elif self.right:
            return _depth + self.right.total_depth(_depth=_depth + 1)

        else:
            return _depth

You can also shorten this like so.

def total_depth(self, _depth=1):

    left_depth  = self.left.total_depth(_depth=_depth + 1)  if self.left else 0
    right_depth = self.right.total_depth(_depth=_depth + 1) if self.right else 0

    return left_depth + right_depth + _depth

In both case you can then get the total depth like this.

tree.total_depth()
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

hi, unfortunately i am aware of how to get max depth. I am indeed looking for total depth. I need both for a run time assignment
thank you! i had an idea to use an argument but couldn't figure it out!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.