Coders Packet

Finding maximum depth of binary tree in Python

By Vedant Keshav Jadhav

This is a simple python code to find the depth (maximum) of a given binary tree. The algorithm used is a simple recursive approach and the problem is solved in O(n) time, with a single pass.

A binary tree is a very basic and useful data structure. It is a tree-type non-linear data structure with a maximum of two children for each parent. Every node in a binary tree has a left and right reference along with the data element. The node at the top of the hierarchy of a tree is called the root node.

Depth of a binary tree -  The depth of a node in a binary tree is the length of the path from the root of the tree to that node. That is, the root has depth 0, its children have depth 1, its grandchildren have depth 2, and so on. The maximum depth of a binary tree is the distance of the root node of the tree from the furthest node in the tree. For example:

As we can see in the figure, the furthest node is at level 4, hence the depth of the binary tree is 4.

 

Algorithm to find the maximum depth:  The algorithm used here is a simple recursive approach. Here for every node, we check the depth of it's left and right subtrees. The subtree having greater depth will, in turn, contribute to the maximum depth of the binary tree. The code is -

 

def calc_max_depth(root):
    //If the node is null, then it will not contribute to the depth. 
    if root == None:
        return 0

    //If only the root node is present, the tree will have depth 0.
    if root.left == None and root.right == None:
        return 0
    
    //Calculating the depth of left and right subtree
    left = calc_max_depth(root.left)
    right = calc_max_depth(root.right)

    //Returning the maximum of the left and right subtree. One is added to account for the current depth.
    return max(left, right) + 1

 

Time Complexity - The time complexity of the algorithm is O(n) as we are traversing the entire tree only once.

Space Complexity - The space complexity of the algorithm is O(1), as we are not using any additional data structure to store any values.

 

Python program - The Python code contains driver code along with the main algorithm. The driver code includes code to create the binary tree, print the binary tree, node create, and the main function calls.

Input - The input to the code should be a string containing the list of nodes of the binary tree, the nodes being in depth-first order. For example, for the given binary tree

The input will be - [0, 1, null, null, 0, 1, 1, null, null, 1, null, null, 0]

Output - The output will be a string of the format, "Max depth of given binary tree - x", where x is the maximum depth of the binary tree.

In this case, the output will be, "Max depth of given binary tree - 3".

Download Complete Code

Comments

No comments yet