• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / Data Structures / Find the Height of a Binary Tree

Find the Height of a Binary Tree

Author: Aditya Raj
Last Updated: September 15, 2021

Just like we find the length of a list or the number of items in a python dictionary, we can find the height of a binary tree. In this article, we will formulate an algorithm to find the height of a binary tree. We will also implement the algorithm in python and execute on a given binary tree.

What is the height of a binary tree?

Height of a binary tree is defined as the maximum distance from the root node at which a node is present in the binary tree. The height of a binary tree depends on the number of nodes and their position in the tree. If a tree has an ā€˜n’ number of nodes, it can have a height anywhere between log(n) + 1 to n.  The binary tree will have a height n if the tree is entirely skewed to either left or right. It will have a height of log(n)+1 if the nodes in the tree are properly distributed and the tree is a complete binary tree.

For example, the following binary tree has 7 elements.A binary tree with 7 elements can have any height between log(7)+ 1 that is 3 and 7. In our example, the nodes of the tree are properly distributed and the tree is completely balanced. Therefore, the height of the tree is 3.

height of a binary tree
binary tree

How to calculate the height of a binary tree?

To calculate the height of a binary tree, we can calculate the heights of left and right subtrees. The maximum of the height of the subtrees can be used to find the height of the tree by adding one to it. For an empty root, we can say that the height of the tree  is zero. Similarly, height of a single node will be considered as 1. 

Algorithm to find the height of a binary tree

Now that we have found a way to find the height of the binary tree, we will formulate the algorithm for finding the height as follows.

  1. If we find an empty root node, we will say that the height of the tree is 0.
  2. Otherwise, we will find the height of the left subtree and right subtree recursively.
  3. After finding the height of the left subtree and right subtree, we will calculate their maximum height.
  4. We will add 1 to the maximum height. That will be the height of the binary tree.

Implementation of the algorithm in Python

Now that we have understood and formulated the algorithm, we will implement it in Python.

from queue import Queue


class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def height(root):
    if root is None:
        return 0
    leftHeight=height(root.leftChild)
    rightHeight=height(root.rightChild)
    max_height= leftHeight
    if rightHeight>max_height:
        max_height = rightHeight
    return max_height+1


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Height of the binary tree is:")
print(height(root))

Output:

Height of the binary tree is:
3

Here, we have created a binary tree node. Then, we defined functions to insert elements to the binary tree. Finally, we implemented the algorithm to find the height of a binary tree in Python.

Conclusion

In this article, we have implemented an algorithm to find the height of a binary tree. To learn more about  other data structures, you can read this article on Linked List in Python. Stay tuned for more articles on implementation of different algorithms in Python.

Related

Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.

Enroll Now

Filed Under: Data Structures Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup bitly Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary – How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehensions in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Pandas Append Row to DataFrame
  • Convert String to DataFrame in Python
  • Pandas DataFrame to List in Python
  • Solved: Dataframe Constructor Not Properly Called Error in Pandas
  • Overwrite a File in Python

Copyright © 2012–2023 Ā· PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us