Tree: Height of a Binary Tree

  • + 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!