As I work through solving DSA problems daily, I often encounter moments where I realize there’s something important I don’t fully understand, and it exposes a gap in my knowledge. This isn’t something unique to me; it’s part of every programmer’s journey. Today, I found myself in a similar situation again.
This time, it involved understanding the difference between static and instance variables in Java. While this might seem like a basic concept, it has a big impact on how your code behaves, especially when recursion is involved.
Note: This post discusses LeetCode’s problem #543, Diameter of a Binary Tree. If you haven’t solved this problem yet, I suggest trying it out first before reading on.
The problem asks us to find the maximum distance between any two nodes in a binary tree. The solution involves recursively calculating the height of the left and right subtrees and updating a variable that tracks the longest path found during the traversal. A subtle issue arises based on how the variable used to store the diameter is handled.
Let’s compare two code snippets that implement the solution in different ways, paying special attention to how the variable ans is declared and used.
Code 1:
class Solution {
int ans = 0;
public int height(TreeNode root) {
if (root == null)
return 0;
int left = height(root.left);
int right = height(root.right);
ans = Math.max(ans, left + right);
return Math.max(left, right) + 1;
}
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return ans;
}
}
Code 2:
class Solution {
static int ans = 0;
public static int height(TreeNode root) {
if (root == null)
return 0;
int left = height(root.left);
int right = height(root.right);
ans = Math.max(ans, left + right);
return Math.max(left, right) + 1;
}
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return ans;
}
}
At first glance, both solutions seem very similar. They follow the same logic and yield correct results for certain test cases. The main difference lies in how the variable ans is declared.
Let’s start with Code 1, which uses an instance variable for ans.
In this code, every time a new instance of the Solution class is created, a fresh ans variable is also created. Each call to the diameterOfBinaryTree method starts with ans set to 0, ensuring no interference from previous method calls.
In contrast, Code 2 uses a static variable for ans. Static variables are shared across all instances of the class, meaning the value of ans persists between calls to the method. This can cause issues if the method is called multiple times, as the result from one tree might "leak" into the calculation of the next tree’s diameter.
Still confused? Let me explain the difference with an analogy. Think of static variables as a shared whiteboard in a classroom. If one student (instance) writes on the whiteboard, all other students can see it and modify the content. The value remains until it’s explicitly cleared.
On the other hand, instance variables are like individual notebooks. Each student has their own notebook, and what one student writes doesn’t affect the others.
Now, let’s apply what we’ve understood in the following code examples:
class BankAccount {
// Instance variable for account balance
int balance = 0;
// Method to deposit money
public void deposit(int amount) {
balance += amount;
}
// Method to get the current balance
public int getBalance() {
return balance;
}
}
public class Main {
public static void main(String[] args) {
BankAccount account1 = new BankAccount();
BankAccount account2 = new BankAccount();
account1.deposit(100);
System.out.println("Account 1 balance: " + account1.getBalance()); // 100
account2.deposit(200);
System.out.println("Account 2 balance: " + account2.getBalance()); // 200
account1.deposit(50);
System.out.println("Account 1 balance after another deposit: " + account1.getBalance()); // 150
}
}
Output:
Account 1 balance: 100
Account 2 balance: 200
Account 1 balance after another deposit: 150
Here, each BankAccount object has its own independent balance variable. When we deposit money into account1, it doesn’t affect account2, and each account has its own separate balance.
Now, let’s see what happens when we use a static variable:
class BankAccount {
// Static variable for account balance
static int balance = 0;
// Method to deposit money
public void deposit(int amount) {
balance += amount;
}
// Method to get the current balance
public int getBalance() {
return balance;
}
}
public class Main {
public static void main(String[] args) {
BankAccount account1 = new BankAccount();
BankAccount account2 = new BankAccount();
account1.deposit(100);
System.out.println("Account 1 balance: " + account1.getBalance()); // 100
account2.deposit(200);
System.out.println("Account 2 balance: " + account2.getBalance()); // 300
account1.deposit(50);
System.out.println("Account 1 balance after another deposit:
" + account1.getBalance()); // 350
}
}
Output:
Account 1 balance: 100
Account 2 balance: 300
Account 1 balance after another deposit: 350
In this case, since the balance variable is static, it is shared across all instances of BankAccount. When we deposit money into account1, the balance is updated for both account1 and account2 because they are referring to the same variable. There is no isolation between the objects.
The key takeaway is that instance variables allow each object to have its own separate state. In the BankAccount example, account1 and account2 have independent balances. The operations on one account do not affect the other account’s balance. Each object operates independently, and their internal state is not shared.
Static variables, on the other hand, are shared among all instances of the class. In the second BankAccount example, the balance is a shared resource. Every operation on account1 or account2 modifies the same balance, and all instances reflect these changes. There is no isolation between the objects.
Understanding the distinction between these two is crucial in programming, especially when dealing with recursive functions or algorithms like the binary tree diameter problem. Static variables persist across method calls and can lead to errors if they are not properly reset, while instance variables provide a clean slate with every new object.
By understanding and properly managing variable scope, you can avoid subtle bugs and make your code more reliable. I encourage you to experiment with static and instance variables in your own code to get a better grasp of their behavior. This will help you build a solid foundation for tackling more complex programming challenges.
Top comments (0)