Search code examples
python-3.xbinary-search-tree

I'm not sure why i am getting None when calculating height of a binary search tree


Here are the class definitions for class Node and class BinarySearchTree

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

My insert function looks like this:

def insert(self, value):
    if self.root is None:
        self.root = Node(value)
    else:
        self._insert(self.root, value)

def _insert(self, curr_node, val):
    if val < curr_node.val:
        if curr_node.left is None:
            curr_node.left = Node(val)
        else:
            self._insert(curr_node.left, val)
    elif val > curr_node.val:
        if curr_node.right is None:
            curr_node.right = Node(val)
        else:
            self._insert(curr_node.right, val)
    else:
        print('Value already exist')

Here is my height function:

def height(self):
    if self.root is None:
        return 0
    else:
        self._height(self.root, 0)

def _height(self, curr, height):
    if curr is None:
        return height
    left_height = self._height(curr.left, height+1)
    right_height = self._height(curr.right, height + 1)
    return max(left_height, right_height)

When I call the height function I get None as the result


Solution

  • def height(self):
        if self.root is None:
            return 0
        else:
            self._height(self.root, 0)
    

    should be

    def height(self):
        if self.root is None:
            return 0
        else:
            return self._height(self.root, 0)