How to find the height of binary tree ? program (Python)

The height of binary tree is defined as MAX(depth of leaf nodes)  and depth of a node in turn is defined as (n-1) ,where n = the least number of nodes traversed through, to reach that node.
For detailed information on Implementing binary tree in python : refer here.



Definition of height function:

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

def _height(self, cur_node, cur_height):
    if cur_node == None: return cur_height
    left_height = self._height(cur_node.left_child, cur_height + 1)
    right_height = self._height(cur_node.right_child, cur_height + 1)
    return max(left_height, right_height)
Here, two functions are used one is used to check that if the binary tree exists or not , if exists then it will call the recursive function to traverse the left branch and right branch depth with respect to the root node , and then returns the bigger of the two by comparing. The value of depth(height ) of tree will be (returned value -1) to deduct the count of root node.

SOURCE CODE :
 # https://www.qxcoding.com/ 

class node:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None
        self.right_child = None


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

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

    def _insert(self, value, cur_node):
        if value < cur_node.value:
            if cur_node.left_child == None:
                cur_node.left_child = node(value)
            else:
                self._insert(value, cur_node.left_child)
        elif value > cur_node.value:
            if cur_node.right_child == None:
                cur_node.right_child = node(value)
            else:
                self._insert(value, cur_node.right_child)

        else:
            print("already exists")

    def print_tree(self):
        if self.root != None:
            self._print_tree(self.root)

    def _print_tree(self, cur_node):
        if cur_node != None:
            self._print_tree(cur_node.left_child)
            print(cur_node.value)
            self._print_tree(cur_node.right_child)

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

    def _height(self, cur_node, cur_height):
        if cur_node == None: return cur_height
        left_height = self._height(cur_node.left_child, cur_height + 1)
        right_height = self._height(cur_node.right_child, cur_height + 1)
        return max(left_height, right_height)

    def delete_tree(self):
        self.root = None
        # freeing the memory will be taken care by garbage collector


if __name__ == '__main__':
    b1 = BinaryTree()
    b1.insert(5)
    b1.insert(10)
    b1.insert(6)
    b1.insert(8)
    b1.insert(3)
    b1.insert(4)
    b1.insert(2)
    b1.print_tree()
    b1.delete_tree()

if any doubts or queries please comment 🙂

Comments

Popular posts from this blog

Python and C++ program to implement multiplication of 2d array (Matrix multiplication)

What is AI (Artificial Intelligence )? and its characteristics

How to find and replace a node in Linked List