We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
It's perhaps a little confusing / unclear that a tree with a "root" of null is considered as being of depth -1. However note the following:
Whilst intuitively you might think to return 0 at this point, the height of a null tree is definitely NOT0! A tree of height 0 is a tree with a single (i.e. root) node.
The constraints specify that the number of nodes is >= 1. The tree will always have a depth >= 0. This means that the only null case you need to code for is the case where you traverse to the end of the tree. Without this constraint, the author would have had to specify how to handle the special case of a "null tree".
With that in mind, returning -1 when you encounter null makes sense - you have in effect gone "beyond" the bounds of the tree. Decrementing the height accounts for this.
My (Java) solution:
publicstaticintheight(Nodenode){if(node==null){// a null node is not part of the tree, so discount itreturn-1;}else{// search recursively, increment depth by 1returnMath.max(height(node.left)+1,height(node.right)+1);}}
I modified the name of the Node parameter from root to node to make it easier for the reader to understand - this function is called recursively from any point on the tree, not just the root.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tree: Height of a Binary Tree
You are viewing a single comment's thread. Return to all comments →
Full solution can be found at clormor/hacker-rank-solutions.
It's perhaps a little confusing / unclear that a tree with a "root" of null is considered as being of depth
-1
. However note the following:0
at this point, the height of anull
tree is definitely NOT0
! A tree of height0
is a tree with a single (i.e. root) node.>= 1
. The tree will always have a depth>= 0
. This means that the onlynull
case you need to code for is the case where you traverse to the end of the tree. Without this constraint, the author would have had to specify how to handle the special case of a "null tree".With that in mind, returning
-1
when you encounternull
makes sense - you have in effect gone "beyond" the bounds of the tree. Decrementing the height accounts for this.My (Java) solution:
I modified the name of the
Node
parameter fromroot
tonode
to make it easier for the reader to understand - this function is called recursively from any point on the tree, not just the root.