Tree: Height of a Binary Tree

  • + 45 comments

    For anyone having problem in sample test case. Please note down that they have considerd height of root as '-1'. So your program should return '-1' when root is NULL.

    • + 1 comment
      [deleted]
      • + 2 comments
        [deleted]
        • + 0 comments

          link doesnt work

        • + 1 comment

          here is the updated problem solution in java python c++ and c programming.

          HackerRank Tree: height of a binary tree solution

    • + 2 comments

      Hm, I've returned 0 in this case and it works

      • + 1 comment

        how it works?

        • + 3 comments

          Sorry, have'nt seen your reply such a long time:

          static int height(Node root) {
                	if(root == null)
                      return 0;
                      
                      //some code then
          

          My code returns 0 when root is NULL and I had no problems with it. Maybe it was fixed later.

          • + 0 comments

            Yeah thats not correct. Should return -1 if root is null and 0 if there is a root with its left and right null.

          • + 1 comment

            still fails with zero when root is null.

            • + 0 comments

              return -1 when root is null

          • + 0 comments

            you should return -1. becz they Assuming height of root as '-1'.

      • + 1 comment

        can u explain me ?

        • + 1 comment
          [deleted]
          • + 1 comment
            [deleted]
            • + 1 comment

              They said The Height of binary tree with single node is taken as zero. So, when we will have no node we will going to return -1

              • + 1 comment

                it all depends on the traversal. If you are using -1, code would be

                if(head==NULL)
                    return -1;
                int leftcount= 1+height(root->left);
                

                now, if you want to use 0 then, code would be

                  if(head==NULL)
                    return 0;
                if(root->left!=NULL)
                    int leftcount= 1+height(root->left);
                
                • + 0 comments

                  why we adding +1 to it

    • + 0 comments

      That was really helpful ... thank you :)

    • + 0 comments

      Yup, that was it.

    • + 2 comments

      NO. they haven't mentioned that in the problem. but in editorial they return -1 for root == Null because:

      def height(root):
          if root:
              return 1 + max(height(root.left), height(root.right))
          else:
              return -1
      

      because they return 1 + max(root.left+root.right) now if root.left or root.right were null then max(blah blah) will return -1 and together they would return 0 as height of that root without left or right subtree..

      • + 0 comments

        Yes, you are right;

        orelse, it return the height+1

      • + 7 comments

        Seriously, who solved the problem without looking reading discussion?

        • + 1 comment

          me

          • + 1 comment

            my solution static int h=0; static int t = 0; static int[] a = new int[40]; static int i=0; public static int height(Node root) { // Write your code here. a[i] = root.data; i++; if(root!=null) {
            if(root.left!=null) { h++; height(root.left); } if(root.right!=null) { h++;
            height(root.right); } if(root.left==null&&root.right==null) { if(h>t) t = h; }

                  }
                  if(root.data==a[0])
                  {
                      return t;
                  }         
                return  h--;
            
        • + 0 comments

          I solved it :)

        • + 0 comments

          Me

        • + 4 comments

          Me using python and implementing level order traversal using arrays to store values of nodes at particular height. List of nodes(n2) are stored in List of tree(n). It will also give you which nodes are present at what level.

          from collections import deque
          def height(root):
              queue=deque()
              queue.append(root)
              n=[]
              n.append([root.info])
              n2=[1]
              while(queue):
                  n1=[]
                  for i in range(len(n2)):
                      current=queue.popleft()
                      if(current.left!=None):
                          queue.append(current.left)
                          n1.append(current.left.info)
                      if(current.right!=None):
                          queue.append(current.right)
                          n1.append(current.right.info)
                  n2=n1
                  if(len(n2)!=0):
                      n.append(n2)
              return len(n)-1
          
          • + 0 comments

            great!!

          • + 1 comment

            def height(root): if root is None: return -1 else: lDepth = height(root.left) rDepth = height(root.right) if(lDepth > rDepth): return lDepth + 1 else: return rDepth + 1

            • + 0 comments

              Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1

        • + 0 comments

          me

        • + 0 comments

          proud to say I solved it without looking! :D

        • + 0 comments

          i solved ,but not seriously..

    • + 0 comments

      Thanks, it was helpful.

    • + 0 comments

      yes ..thanks

    • + 0 comments

      Thank man

    • + 0 comments

      Thaanks!!

    • + 0 comments

      thank you

    • + 2 comments
      public static int height(Node root) {
            	if(root==null)
                  return -1;
              else
                  return 1+(height(root.left)>height(root.right)?height(root.left):height(root.right));
          }
      
      • + 2 comments

        I have similar solution like you. this is very easy problem now I got to learn more about recursion.

        	 if(root==null) {
                return 0; 
            }
            if(root.left==null&&root.right==null) {
                return 0; 
            }
            return Math.max(height(root.left)+1, height(root.right)+1); 
            }
        
        • + 0 comments

          i just wanted to know what accepts the return value here

      • + 1 comment

        If the height is initlaised as -1 then the output is always one less than the actual height

        • + 1 comment

          You're not initialising the height at -1, the -1 happens at the end of the recursive loop. It is required, because when you hit a null node you have effectively gone beyond the bounds of what constitutes a valid tree.

          It's hard to imagine an analogy, but let's say you were blindfolded and had to count a row of items placed in front of you. Maybe there are ten stones and a rubber duck, and you have to count the number of stones. You touch each item with your hand and count one.. two.. thre... until you count the duck. In your head you have reached 11, but because the duck is not a stone you have to subtract one to get back to 10.

          Ok rubbish analogy, but the principle is the same here. My solution posted here is very similar to these algorithms, and it works for all the provided test cases, and in fact would work correctly on any input (within the constraints).

          Think of it another way - If you return 0 for a null node then the code is definitely wrong, because a null tree does not have a height of 0. A tree of height 0 is a valid tree with one node - the root. That is different from a tree where the root node is null.

          • + 1 comment

            Hey Clormor, This is the submission I made and it works perfectly Ok with 0 as default height for null tree public static int height(Node root) {

            if (root == null) { return 0; } if (root.left == null && root.right == null) { return 0; } return Math.max(height(root.left) + 1, height(root.right) + 1);

            }

            • + 0 comments

              [EDIT] @mulshankar13, you are not setting the default height of a null node to 0; you are however setting it to 0 in cases where there is guaranteed to be another valid branch of greater height.

              Because of your if (root.left == null && root.right == null) {...} block, your if (root==null) {...} check is only called on a node with one branch. In this case the other branch has a non-null node and is guaranteed to have a greater height than the current branch. Knowing this, you can get away with returning 0 instead of -1.

              If you change your code to return -1 when root==null then it will still pass all the tests. Equally, if you were to remove the if (root.left == null && root.right == null){...} block, then you would have to return -1 when root == null. Sorry to labour the point, but I think understanding this concept and why your code can get away with returning 0 will make it easier for you to solve future tree-related problems.

              In my previous (very bad!) analogy, you have effectively taken off your blindfold - once you count the 10th stone, you see that up next there is a rubber duck so you stop counting. I would argue that the way others have implemented it is cleaner and easier to understand because your loop is simultaneously comparing both the node and the node's children - other solutions follows a more typical recursive pattern. But it still returns the right answer, so kudos!

    • + 0 comments

      thanks bro it really helped i was getting that error but reading the first comment only solved it thank you very much.

    • + 0 comments

      Dude! this helped me so much -- thanks.

    • + 0 comments

      https://youtu.be/t7aWsLlN8aY

      Faster Solution !!

    • + 0 comments

      I returned 0 and it works well with all test case passed. if(root==null) then return 0;

    • + 0 comments

      thank you it really helped

    • + 0 comments

      Thank you .. I had missed it and was looking for what was the problem..

    • + 0 comments

      That is not quite accurate - the height of the root node is 0. However for the reasons I outline in my post here you are right to point out that you must return -1 when you encounter a null node. You are guaranteed never to see null at the root of the tree.

    • + 0 comments

      thanks bro

    • + 0 comments

      Thanks, that's really help

    • + 0 comments

      Thanks brother.

    • + 0 comments

      def height(root): if root == None: return(-1) else: return(ht(root)) def ht(node):
      if node != None: ldepth = height(node.left) rdepth = height(node.right) if ldepth > rdepth: return ldepth+1 else: return rdepth+1
      else: return (0)

    • [deleted]
      + 0 comments

      yes, I realized this after several attempts.

    • + 0 comments

      thanks bro

    • + 0 comments

      Is the reason why there should be a -1 because it is always recursively called one more time than it should be causing it to +1 an extra time?

    • + 0 comments

      Thank You

    • + 0 comments

      Thanks a lot!

    • + 0 comments

      I just added this line

      if(root->left == NULL && root->right == NULL) {
                  return 0;
      
          }
      
    • + 0 comments

      Thanks.

    • + 0 comments

      No, they have counted root node as 0, and empty tree with no node as -1.

      The reason we have to return -1 when (root == null) is that, through recursion we are incrementing count for each node including root node, whereas defination of height is the number of edges connecting root to the farthest leaf, which will clearly be 1 less.

      if (root == null){ return -1; } else{ return 1 + Math.max( getHeight(root.left), getHeight(root.right) ); }

    • [deleted]
      + 0 comments

      my output showing 4. so what i do?

    • + 0 comments

      Thanks a lot Brother. This comment saved my time.

    • + 0 comments

      yeah right. thanks for the information.

    • + 0 comments

      Thanks.

    • + 0 comments

      they considered height of root as 0

    • + 0 comments

      Thanks, this really helped me

    • + 0 comments

      The height of a binary tree with no children is 0. If you are returning -1 in this case, that only works if you also have somewhere that adds +1 so the final return value becomes 0.

    • + 0 comments

      My working C++ solution

          int height(Node* root) {
              if(root == NULL)
                  return -1;
              return max(1 + height(root->left), 1 + height(root->right));
          }
      
    • + 0 comments

      No one has considered the height of root as -1. The height of the tree is represented as the edges that connects them rather than the number of nodes themselves, so that is why the solution contains -1 when root is null, to subtract 1 from the longest number nodes to instead get the number of edges.

    • + 0 comments

      Always i found a good person like you Thanks

    • + 0 comments

      True Bro!!.

    • + 0 comments

      Yes thats why i wasted my 30 min i thought my solution is wrong