CODEWITHSUNDEEP
javabinary-tree
Newbie
Newbie

Reputation: 2728

Maximum Height of a Binary Tree

Hi I came across a code to find the maximum height of a binary tree. In this code why is there a +1 in the return statement?

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

Upvotes: 1

Views: 1490

Answers (2)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522762

Consider a tree consisting of a single root node. Then the following return statement would return 1, which is what we expect:

return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
return Math.max(0, 0) + 1;
return 1;

As your base case shows, an empty tree would have a height of zero, and you can build up to taller trees' height using induction.

Upvotes: 1

Eran
Eran

Reputation: 394146

If there wasn't, the result would always be 0.

The max height of a binary tree is the max height of the child having a larger max height (that's the Math.max(maxDepth(root.left), maxDepth(root.right)) part) + 1 for the root of the tree.

Upvotes: 2

Related Questions