## DEV Community is a community of 868,017 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Meta Verse

Posted on • Updated on

# 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)
``````

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);

}
}
``````

#### 1. Recursive traversal

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

#### 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;

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();

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

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

}

return resultList.size();

}
``````

#### 3. Iterative traversal using height variable

``````private int maxDepth_usingHeightVariable(TreeNode root){

if(root == null) return 0;

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;
}
``````

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

#### Related problems

Problem Credit : leetcode.com