Solution by itzpriyanka.rani34


  • 0
    I

    Approach #1 Iterative [Accepted]

    Intuition and Algorithm

    Idea is to traverse level by level. Whenever moving down to another level, increment height by 1 (height is initialized as 0),remove nodes of this level and add nodes of
    next level. Count number of nodes at each level, stop traversing when count of nodes at next level is 0.

    Java

    public int maxDepth(TreeNode root) {
           if(root==null){
               return 0;
           }
           Queue<TreeNode> q=new LinkedList();
           q.add(root);
           int height=0;
           while(1==1){
               int count=q.size();
               if(count==0){
                   return height;
               }
               height++;
               while(count>0){
                   TreeNode newnode = q.peek();
                   q.remove();
                   if (newnode.left != null)
                       q.add(newnode.left);
                   if (newnode.right != null)
                       q.add(newnode.right);
                   count--;
               }
               
           }
    

    Complexity Analysis

    • Time complexity : O(n).

    • Space complexity : Maximum Space can be o(2^d). Where d is the depth of the tree.

    Note
    There are other iterative aproach using stacks,In-order traversal, Post-order Traversal.
    Refer:- https://articles.leetcode.com/maximum-height-of-binary-tree/


    Approach #2 Recursion [Accepted]

    Idea is to first compute the max height of left sub-tree, then compute the max height of right sub-tree. Therefore, the max height of the current node is the greater of the two max heights + 1. For the base case, the current node is NULL, we return zero. NULL signifies there is no tree, therefore its max height is zero.

    Algorithm

    Java

    public class Solution {
       public int maxDepth(TreeNode root) {
        if(root==null){
              return 0;
          }
          int l=maxDepth(root.left)+1;
          int r=maxDepth(root.right)+1;
          int max=Math.max(l,r);
          return max;
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n).

    • Space complexity : No additional space other than recursion overhead stack space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.