Implement a binary search tree as described in the course material, but with the addition of the method height
that returns the height of the tree.
The height of a tree is the largest depth of any node in the tree. In other words, the height is the number of edges on the longest path from the root to a leaf. If the tree is empty, the height is .
Start with the implementation in the course material and add the member variable max_depth
to the class. The value of the variable is updated if needed with each call to the method add
. The method height
can simply return the value of the variable.
In a file treeheight.py
, implement the class TreeSet
according to the following code template. Your task is to fill in the method add
. You can take the implementation in the course material and modify it appropriately.
class Node: def __init__(self, value): self.value = value self.left = None self.right = None class TreeSet: def __init__(self): self.root = None self.max_depth = -1 def add(self, value): # TODO def height(self): return self.max_depth if __name__ == "__main__": numbers = TreeSet() print(numbers.height()) # -1 numbers.add(2) print(numbers.height()) # 0 numbers.add(1) print(numbers.height()) # 1 numbers.add(3) print(numbers.height()) # 1 numbers.add(4) print(numbers.height()) # 2