How to avoid using global/class level variables in recursion?

user_17107099 0
Viewed 150

Recursive solutions become easy if the methods keep using/updating a global variables but it become complex when you need to pass that variable onto recursion stack.

Following is a recursive solution(java) for a leetcode problem 250. Count Univalue Subtrees.

You can refer to the problem for a better understanding. My solution works just fine. I want to avoid using the global variable.

Problem statement:

Given the root of a binary tree, return the number of uni-value subtrees. A uni-value subtree means all nodes of the subtree have the same value.

  • Example 1

Input: root = [5,1,5,5,5,null,5] Output: 4

  • Example 2

Input: root = [] Output: 0

  • Example 3

Input: root = [5,5,5,5,5,null,5] Output: 6

/**
 * 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 {

  int uniCount; // class level variable to keep the count of uni-valued tree/sub-tree

  public int countUnivalSubtrees(TreeNode root) {
    uniCount = 0;
    recurseAndUpdate(root);
    return uniCount;
  }


  private boolean recurseAndUpdate(TreeNode root) {

    if (root == null) {
      return true;
    }

    if (root.left == null && root.right == null) { // If root is a leaf node
      uniCount++;
      return true;
    } else if (root.left == null && root.right != null) { // If root has only right child
      boolean currRes = root.val == root.right.val;
      boolean rightRes = recurseAndUpdate(root.right);

      if (currRes && rightRes) {
        uniCount++;
        return true;
      }

    } else if (root.left != null && root.right == null) { // If root has only left child

      boolean currRes = root.val == root.left.val;
      boolean leftRes = recurseAndUpdate(root.left);

      if (currRes && leftRes) {
        uniCount++;
        return true;
      }

    } else { // If root have both the left & right child

      boolean currRes = root.val == root.left.val && root.val == root.right.val;
      boolean leftRes = recurseAndUpdate(root.left);
      boolean rightRes = recurseAndUpdate(root.right);

      if (currRes && leftRes && rightRes) {
        uniCount++;
        return true;
      }

    }

    return false;

  }

}

In above recursive function recurseAndUpdate(TreeNode root), class variable uniCount is being updated depending upon some constraints.

How can I get rid of using this global variable nd come up a solution like recurseAndUpdate(TreeNode root, int uniCount) ? How can deduce the approach for such recursive logic that tends to pass some value in nested recursive call?

binary-tree recursion algorithm java
2 Answers

You can define a class for your counter first, then easily pass it to the recursive function. For example like follow:

// define a class as a wrapper
class RecursiveCounter {
    int value;
    public RecursiveCounter(){
        value = 0;
   }
}

// modify the current solution class as follows

// remove the global variable

private boolean recurseAndUpdate(TreeNode root, RecursiveCounter uniCount) {
// replace all uniCount to uniCount.value
// Also, pass the same uniCount variable to all recursive calls
// ...
}

public int countUnivalSubtrees(TreeNode root) {
    RecursiveCounter uniCount;
    recurseAndUpdate(root, unitCount);
    return uniCount.value;
}
user_37688710

Your recursive function currently returns a boolean to indicate whether the subtree is monotone. You could instead let it return the number of monotone subtrees in that subtree, and make that number negative when it itself is not a monotone subtree.

This way you have recursive function that returns the two informations in one package:

  • A non-negative number indicates that the subtree is monotone (or empty) and consists of that many nodes.

  • A negative number indicates that the subtree is not monotone and has that many (in absolute value) subtrees that are monotone.

It is not difficult to adapt your code to make it work like that. Your wrapper function will then just have to return the absolute value of the value coming from the top call of the recursion tree.

I had a go at it, but I did reduce the code somewhat -- avoiding code repetition:

  public int countUnivalSubtrees(TreeNode root) {
    return Math.abs(recurseAndUpdate(root));
  }

  private int recurseAndUpdate(TreeNode root) {
    if (root == null) {
      return 0;
    }
    boolean current = (root.left == null || root.val == root.left.val) && 
                      (root.right == null || root.val == root.right.val);
    int leftRes = recurseAndUpdate(root.left);
    int rightRes = recurseAndUpdate(root.right);
    return leftRes < 0 || rightRes < 0 || !current 
        ? -Math.abs(leftRes) - Math.abs(rightRes)
        : leftRes + rightRes + 1;
  }
user_54598390
Related