Why is recursion causing the count to return 2 instead of 4?

Question

I am trying to do the Balanced Tree question on Leetcode where you return true only if height of left subtree - height of right subtree <= 1. Why is the depth of the left subtree returning a 2 when it should return 4? Is there something I am interpreting wrongly? I attached a picture of the tree at the bottom.

Input: [1,2,2,3,3,null,null,4,4,null,null,5,5]

Output: True (because left subtree is returning 2 instead of 4)

Expected Output: False

Print Statements:

left subtree: 2

right subtree: 1

result: 1 (left subtree - right subtree)

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
    // 1 2 2 3 3 4 4
    // 
      
    if (root == null) return true;
    System.out.println("left subtree: " + findDepth(root.left,1));   
    System.out.println("right subtree: " + findDepth(root.right,1));   
    System.out.println("result: " + Math.abs(findDepth(root.left,1) - findDepth(root.right, 1)));
    if ( Math.abs(findDepth(root.left,1) - findDepth(root.right, 1)) <= 1) return true;
    return false;
    }
  
  public static int findDepth(TreeNode root, int count) {
    if (root == null) return count;
    if (root.left != null) {
       count++;
       findDepth(root.left, count);
    }
     if(root.left == null && root.right == null) return count;

    return count;
  }
    
}

Image of Binary Tree

Does [this](https://stackoverflow.com/questions/1876255/how-to-calculate-the-depth-of-a-binary-search-tree) answer your question? — Sweeper, Jul 10 '21 at 05:47
@Sweeper based on the debugger, the count reaches 4 then starts decreasing to 2. I am not sure why it would decrease when there is no count-- anywhere in the code. I'd like to understand why the recursion is decreasing the counter. — jstarr34, Jul 10 '21 at 05:51

HandsomeCoder · Answer 1 · 2021-07-10T06:01:09.867

0

Because you are only counting the depth of the left side of the tree in findDepth methof by applying condition

if (root.left != null) {
   count++;
   findDepth(root.left, count);
}

You can modify your method like this

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

edited Jul 10 '21 at 06:01

answered Jul 10 '21 at 05:53

HandsomeCoder

726
5
8

if (root.left != null || root.right != null) { count++; findDepth(root.left, count); findDepth(root.right, count); } why does this not do anything? and thanks I'd like to upvote your comment but do not have enough reputation points! – jstarr34 Jul 10 '21 at 06:03
Thanks... it will work if you read the return value from the `findDepth` method because when you pass the value to the function and then whatever happens inside the `method` with that value won't be reflected back as it is `pass by value` not `pass by reference` – HandsomeCoder Jul 10 '21 at 06:15

score 0 · Accepted Answer · answered Jul 10 '21 at 06:11

The reason why you get 2 is because when you recurse, the recursive call is not incrementing the count variable that you pass in. Instead, it increments its own copy of it. Java is pass by value.

if (root.left != null) {
   count++;
   // the call below will not change "count" at all
   findDepth(root.left, count);
   // it will only change its own copy
}

Therefore, the recursive call practically does nothing. You are not even using its return value. Its return value is actually the modified copy of count that you want count to be set to, so to fix this, set count to the return value of findDepth:

value = findDepth(root.left, count);

This will give you the expected 4, but your findDepth should also check the right subtree, and can be improved in other ways. For example, you don't actually need a count argument.

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

Why is recursion causing the count to return 2 instead of 4?

2 Answers2