DEV Community

ashutosh049
ashutosh049

Posted on • Edited on

4 2

Binary Tree: Maximum Depth/Height Of Deepest Node using recursive and iterative way

Hello fellow programmers.

I have started to pile my learnings for DSA here on Dev.to platform.

Module: Binary Tree

You can refer to the Leetcode problem 104. Maximum Depth of Binary Tree

Problem Statement

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

    (3)
 /      \
(9)     (20)
       /    \
    (15)     (7)
Enter fullscreen mode Exit fullscreen mode

Input: root = [3,9,20,null,null,15,7]
Output: 3

The calling function

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        //return maxDepth_Recursive(root);
        //return maxDepth_Iterative_BFS(root);
        return maxDepth_usingHeightVariable(root);

    } 
}
Enter fullscreen mode Exit fullscreen mode

1. Recursive traversal

 private int maxDepth_Recursive(TreeNode root){
   if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) +1;
 }
Enter fullscreen mode Exit fullscreen mode

2. Iterative BFS

We can use BFS to get the highest level(deepest node). Implement BFS, return the size of the List of level nodes.

Check this question for more into on 102. Binary Tree Level Order Traversal

private int maxDepth_Iterative_BFS(TreeNode root){

    List<List<Integer>> resultList = new ArrayList<>();

     if(root == null) return 0;

    TreeNode curr = root;

    Queue<TreeNode> q = new LinkedList<>();

    q.offer(curr);

    while(!q.isEmpty()){
        int qSize = q.size();
        List<Integer> subList = new ArrayList<>();

        for(int i=0; i< qSize; i++){
            curr = q.poll();

            subList.add(curr.val);

            if(curr.left != null){
                q.offer(curr.left);
            }

            if(curr.right != null){
                q.offer(curr.right);
            }
        }
        //add to main list
        resultList.add(subList);

    }

    return resultList.size();

}
Enter fullscreen mode Exit fullscreen mode

3. Iterative traversal using height variable

private int maxDepth_usingHeightVariable(TreeNode root){

     if(root == null) return 0;

    Queue<TreeNode> q = new LinkedList<>();

    q.offer(root);
    int maxDepth = 0;

    while(!q.isEmpty()){

        maxDepth++;
        int i = q.size();
        while(i-- > 0){

         TreeNode curr = q.poll();

         if(curr.left != null){
            q.offer(curr.left);
         }

         if(curr.right != null){
            q.offer(curr.right);
         }
        }

    }
    return maxDepth;
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity for all the 3 way : O(n)
Space Complexity for all the 3 way : O(n)

Related problems

  1. 102. Binary Tree Level Order Traversal
  2. 987. Vertical Order Traversal of a Binary Tree
  3. 199. Binary Tree Right Side View
  4. 107. Binary Tree Level Order Traversal II
  5. 94. Binary Tree Inorder Traversal

Problem Credit : leetcode.com

Image of Bright Data

Feed Your Models Real-Time Data – Enhance your AI with up-to-the-minute data.

Utilize our live data feeds for dynamic model training, ensuring your AI systems are always ahead.

Access Real-Time Data

Top comments (0)

Image of Bright Data

Ensure Data Quality Across Sources – Manage and normalize data effortlessly.

Maintain high-quality, consistent data across multiple sources with our efficient data management tools.

Manage Data

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay