DFS Mastery: When to Use Global Variables vs Return Values - Complete Interview Guide

Introduction: A Critical Interview Decision

One of the most confusing aspects of DFS (Depth-First Search) for interview candidates is deciding:

Should I use a global variable, or can I solve this with return values?

This isn’t just a style preference—it’s a fundamental pattern recognition skill that top interviewers evaluate. Making the wrong choice leads to:

❌ Convoluted code that’s hard to debug
❌ Wrong answers due to Java’s pass-by-value pitfalls
❌ Interviewer asking “Can you simplify this?”

After 11+ years at Microsoft, Booking.com, and Alibaba, I’ve seen this trip up even strong candidates. This guide gives you a clear decision framework with reusable templates.

The Core Distinction

🌍 Global Variables (Class-Level State)

Use when: You need to accumulate information across multiple branches or track state that transcends the current subtree.

    Root
   /    \
  A      B
 / \    / \
C   D  E   F

Goal: Count all nodes where val > threshold
→ Need to accumulate: C ✓, A ✗, D ✓, ... → Total: 4
   This count spans the entire tree → Global variable

🔄 Return Values (Local Computation)

Use when: The result for a node can be computed from its children’s results and returned upward.

    Root(4)
   /       \
  A(2)     B(6)
 / \       / \
C(1) D(3) E(5) F(7)

Goal: Find max value in tree
→ Max at A = max(C, D) = 3
→ Max at B = max(E, F) = 7
→ Max at Root = max(A, B) = 7
   Each node returns a value to parent → Return value

Pattern 1: When You MUST Use Global Variables

Characteristics

Accumulating results from multiple independent paths
Tracking state during in-order/pre-order/post-order traversal
Counting, collecting, or comparing across branches
Need to maintain “previous” or “best so far” state

Classic Problem: Minimum Absolute Difference in BST

Problem 1: Minimum Absolute Difference in BST (LC 530)

Problem: Given a BST, find the minimum absolute difference between any two nodes.

Why global variable?
You need to track the previous node during in-order traversal:

BST:      4
        /   \
       2     6
      / \
     1   3

In-order: 1 → 2 → 3 → 4 → 6
          ↑   ↑
       prev curr → diff = 2-1 = 1 (minimum!)

The "prev" must persist across recursive calls → Global variable

Template: Java (Global Variable Pattern)

class Solution {
    private int minDiff = Integer.MAX_VALUE;
    private Integer prev = null;  // Previous node value in in-order traversal
    
    public int getMinimumDifference(TreeNode root) {
        inorderDFS(root);
        return minDiff;
    }
    
    private void inorderDFS(TreeNode node) {
        if (node == null) return;
        
        inorderDFS(node.left);  // Visit left subtree
        
        // Process current node
        if (prev != null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;  // Update global prev
        
        inorderDFS(node.right);  // Visit right subtree
    }
}

Template: Python (Global Variable Pattern)

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        self.min_diff = float('inf')
        self.prev = None
        
        def inorder_dfs(node):
            if not node:
                return
            
            inorder_dfs(node.left)
            
            # Process current node
            if self.prev is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev)
            self.prev = node.val
            
            inorder_dfs(node.right)
        
        inorder_dfs(root)
        return self.min_diff

Template: JavaScript (Global Variable Pattern)

var getMinimumDifference = function(root) {
    let minDiff = Infinity;
    let prev = null;
    
    function inorderDFS(node) {
        if (!node) return;
        
        inorderDFS(node.left);
        
        // Process current node
        if (prev !== null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;
        
        inorderDFS(node.right);
    }
    
    inorderDFS(root);
    return minDiff;
};

Complexity:

Time: $O(n)$ - visit each node once
Space: $O(h)$ - recursion stack height

Why Return Value Doesn’t Work Here

Common mistake:

// ❌ WRONG: Trying to pass prev as parameter
private void dfs(TreeNode node, int prev) {
    if (node == null) return;
    dfs(node.left, prev);
    minDiff = Math.min(minDiff, node.val - prev);
    prev = node.val;  // ❌ This doesn't propagate! (pass-by-value)
    dfs(node.right, prev);
}

Why it fails: In Java, int is pass-by-value. When you update prev = node.val, it only affects the local copy. The next recursive call still sees the old value.

Advanced Example: Convert Sorted List to BST (Inorder Simulation)

Problem 2: Convert Sorted List to BST (LC 109)

Problem: Given a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Why global variable?
The optimal solution uses a brilliant insight: simulate BST inorder traversal while consuming the sorted linked list sequentially.

Linked List: -10 → -3 → 0 → 5 → 9
Indices:      0    1   2   3   4

BST Inorder: Left → Root → Right
List order:  Sequential consumption

Key insight: BST inorder traversal produces sorted sequence!
→ We can build the tree in inorder manner while moving list pointer

The Challenge:
Unlike arrays, we can’t random-access the “middle” of a linked list in O(1). But we can:

Calculate list length: O(n)
Use index range to determine tree structure
Use global pointer to consume list nodes in inorder sequence

Visualization:

Build BST for indices [0, 4], mid = 2

Step 1: Build left subtree [0, 1]
  ├─ [0, 1], mid = 0
  │  ├─ [0, -1] → null
  │  ├─ Create node(-10) ← current points here, move to -3
  │  └─ [1, 1], mid = 1
  │     ├─ [1, 0] → null
  │     ├─ Create node(-3) ← current points here, move to 0
  │     └─ [2, 1] → null

Step 2: Create root node(0) ← current points here, move to 5

Step 3: Build right subtree [3, 4]
  └─ Similar process...

The 'current' pointer must persist across ALL recursive calls!

Template: Java (Inorder + Global Pointer)

class Solution {
    private ListNode current;  // Global: tracks current position in list
    
    public TreeNode sortedListToBST(ListNode head) {
        // Step 1: Calculate list size
        int size = getSize(head);
        
        // Step 2: Initialize global pointer
        current = head;
        
        // Step 3: Build BST using inorder traversal pattern
        return inorderBuild(0, size - 1);
    }
    
    private int getSize(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }
    
    /**
     * Build BST for index range [left, right] using inorder traversal
     * Key: Process nodes in inorder sequence (Left → Root → Right)
     */
    private TreeNode inorderBuild(int left, int right) {
        if (left > right) {
            return null;
        }
        
        int mid = left + (right - left) / 2;
        
        // Inorder Step 1: Build left subtree FIRST
        // This consumes list nodes in sorted order
        TreeNode leftChild = inorderBuild(left, mid - 1);
        
        // Inorder Step 2: Process current node (root of this subtree)
        TreeNode root = new TreeNode(current.val);
        root.left = leftChild;
        current = current.next;  // ⭐ Move global pointer forward
        
        // Inorder Step 3: Build right subtree LAST
        root.right = inorderBuild(mid + 1, right);
        
        return root;
    }
}

Template: Python (Inorder + Global Pointer)

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # Step 1: Calculate list size
        size = self.get_size(head)
        
        # Step 2: Initialize global pointer
        self.current = head
        
        # Step 3: Build BST using inorder traversal
        return self.inorder_build(0, size - 1)
    
    def get_size(self, head: ListNode) -> int:
        size = 0
        while head:
            size += 1
            head = head.next
        return size
    
    def inorder_build(self, left: int, right: int) -> TreeNode:
        if left > right:
            return None
        
        mid = (left + right) // 2
        
        # Inorder: Left → Root → Right
        left_child = self.inorder_build(left, mid - 1)
        
        # Process current node
        root = TreeNode(self.current.val)
        root.left = left_child
        self.current = self.current.next  # Move pointer
        
        root.right = self.inorder_build(mid + 1, right)
        
        return root

Template: JavaScript (Inorder + Global Pointer)

var sortedListToBST = function(head) {
    // Step 1: Calculate list size
    const getSize = (node) => {
        let size = 0;
        while (node) {
            size++;
            node = node.next;
        }
        return size;
    };
    
    const size = getSize(head);
    let current = head;  // Closure captures this variable
    
    // Step 2: Build BST using inorder traversal
    const inorderBuild = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        
        // Inorder: Left → Root → Right
        const leftChild = inorderBuild(left, mid - 1);
        
        // Process current node
        const root = new TreeNode(current.val);
        root.left = leftChild;
        current = current.next;  // Move pointer forward
        
        root.right = inorderBuild(mid + 1, right);
        
        return root;
    };
    
    return inorderBuild(0, size - 1);
};

Complexity:

Time: $O(n)$ - each list node is processed exactly once
Space: $O(\log n)$ - recursion stack for balanced tree

Deep Dive: Why This Works

The Magic of Inorder Traversal:

BST Property: Inorder traversal of a BST yields a sorted sequence

BST:      4          Inorder: [2, 4, 6]
        /   \                  ↑  ↑  ↑
       2     6         Sorted: matches list!

Reverse the Logic: If we build the tree in inorder sequence, we can consume the sorted list sequentially

List pointer moves: -10 → -3 → 0 → 5 → 9
Tree construction:  Left subtree → Root → Right subtree
                    (consumes -10,-3) (0)  (consumes 5,9)

Index Range Trick: We use [left, right] indices to determine tree structure without traversing the list to find midpoints

Range [0, 4], mid = 2 → Root will be the 3rd node (index 2)
Build left [0, 1] first → Consumes nodes at indices 0, 1
Then create root → Consumes node at index 2
Build right [3, 4] last → Consumes nodes at indices 3, 4

Why Global Variable is Essential Here

What if we try to pass current as a parameter?

// ❌ WRONG: Trying to pass current as parameter
private TreeNode build(int left, int right, ListNode current) {
    if (left > right) return null;
    
    int mid = (left + right) / 2;
    TreeNode leftChild = build(left, mid - 1, current);  // ❌
    
    TreeNode root = new TreeNode(current.val);
    current = current.next;  // ❌ Only updates local copy!
    
    TreeNode rightChild = build(mid + 1, right, current);  // ❌ Wrong node!
    return root;
}

Why it fails:

Java passes object references by value
When you do current = current.next, you’re updating the local reference, not the original
After returning from build(left, mid - 1, current), the outer scope still sees the old current
The right subtree would read wrong nodes from the list

The Fix: Use a class-level variable that all recursive calls share:

// ✅ CORRECT: Class-level variable
private ListNode current;

private TreeNode build(int left, int right) {
    // All calls modify the SAME current pointer
    current = current.next;  // ✅ Persists across all calls
}

Alternative Approaches (For Comparison)

Approach 1: Fast-Slow Pointer (O(n log n) time)

// Find middle by traversing list every time
private ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    if (prev != null) prev.next = null;  // Split list
    return slow;
}
// Recursively build: O(n) per level × O(log n) levels = O(n log n)

Approach 2: Convert to Array (O(n) time, O(n) space)

// Copy list to array, then build BST from array
int[] arr = new int[size];
// Extra O(n) space

Our Approach: Inorder Simulation ⭐ Best Time & Space

Time: O(n) - single pass through list
Space: O(log n) - only recursion stack
Elegantly leverages the sorted property!

When to Use This Pattern

This “inorder simulation with global pointer” pattern applies when:

✅ Input is a sequential data structure (list, stream)
✅ Output follows a traversal order (inorder, preorder, etc.)
✅ You need to consume input sequentially while building structure
✅ Random access is expensive or impossible

Similar problems:

Construct BST from Preorder Traversal (LC 1008)
Serialize and Deserialize BST (LC 449)
Construct Tree from Inorder and Preorder (LC 105)

Pattern 2: When Return Values Are Better

Characteristics

Computing properties bottom-up (from leaves to root)
Each node’s result depends ONLY on its children
No need to track state across sibling branches
Tree properties: height, max value, sum, etc.

Classic Problem: Maximum Depth of Binary Tree

Problem 2: Maximum Depth of Binary Tree (LC 104)

Problem: Find the maximum depth (height) of a binary tree.

Why return value?
The depth at each node = 1 + max(left depth, right depth).

Tree:     3
        /   \
       9    20
           /  \
          15   7

Depth(15) = 1 (leaf)
Depth(7)  = 1 (leaf)
Depth(20) = 1 + max(1, 1) = 2
Depth(9)  = 1 (leaf)
Depth(3)  = 1 + max(1, 2) = 3 ✓

Each node computes from children → Return value

Template: Java (Return Value Pattern)

class Solution {
    public int maxDepth(TreeNode root) {
        // Base case
        if (root == null) {
            return 0;
        }
        
        // Recursive case: compute from children
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        // Combine and return
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

Template: Python (Return Value Pattern)

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # Base case
        if not root:
            return 0
        
        # Recursive case: compute from children
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        # Combine and return
        return 1 + max(left_depth, right_depth)

Template: JavaScript (Return Value Pattern)

var maxDepth = function(root) {
    // Base case
    if (!root) return 0;
    
    // Recursive case: compute from children
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    // Combine and return
    return 1 + Math.max(leftDepth, rightDepth);
};

Complexity:

Time: $O(n)$ - visit each node once
Space: $O(h)$ - recursion stack height

Pattern 3: Hybrid Approach (Both Global + Return)

Some problems need both patterns simultaneously!

Example: Binary Tree Maximum Path Sum

Problem 3: Binary Tree Maximum Path Sum (LC 124)

Problem: Find the maximum path sum in a binary tree. A path can start and end at any node.

Why hybrid?

Global variable: Track the overall maximum path sum (could go through any node)
Return value: For each node, return the max single-path sum (can be extended by parent)

Tree:    -10
        /    \
       9     20
            /  \
           15   7

Possible paths:
- 15 → 20 → 7 (sum = 42) ← Maximum! (stored in global)
- 9 alone (sum = 9)
- 15 → 20 (sum = 35)

But when we return to parent (-10):
- Left returns: 9
- Right returns: 35 (20 + max(15, 7))
- We update global max with: 9 + (-10) + 35 = 34

Template: Java (Hybrid Pattern)

class Solution {
    private int maxSum = Integer.MIN_VALUE;  // Global: overall max
    
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        
        // Return value: max single-path gain from children
        int leftGain = Math.max(maxGain(node.left), 0);  // Ignore negative paths
        int rightGain = Math.max(maxGain(node.right), 0);
        
        // Global update: path through current node
        int pathThroughNode = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathThroughNode);
        
        // Return: best single path (can't use both children)
        return node.val + Math.max(leftGain, rightGain);
    }
}

Template: Python (Hybrid Pattern)

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')
        
        def max_gain(node):
            if not node:
                return 0
            
            # Return value: max single-path gain
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            # Global update: path through current node
            path_through_node = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, path_through_node)
            
            # Return: best single path
            return node.val + max(left_gain, right_gain)
        
        max_gain(root)
        return self.max_sum

Template: JavaScript (Hybrid Pattern)

var maxPathSum = function(root) {
    let maxSum = -Infinity;
    
    function maxGain(node) {
        if (!node) return 0;
        
        // Return value: max single-path gain
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);
        
        // Global update: path through current node
        const pathThroughNode = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathThroughNode);
        
        // Return: best single path
        return node.val + Math.max(leftGain, rightGain);
    }
    
    maxGain(root);
    return maxSum;
};

Complexity:

Time: $O(n)$
Space: $O(h)$

Key insight:

Global variable stores the “best path anywhere in tree” (can use both left + right children)
Return value represents “best path extending upward” (can only use one child)

Decision Framework: Quick Reference

Use Global Variable When:

✅ Tracking “previous” or “best so far” across the entire traversal
✅ Accumulating results from multiple branches (count, sum, list)
✅ In-order/pre-order traversal where order matters
✅ Comparing nodes across different subtrees
✅ Need to maintain state that survives returning from recursion

Examples:

BST in-order traversal problems (kth smallest, validate BST)
Path sum collection (all paths that sum to target)
Count nodes satisfying global condition
Serialize/deserialize trees

Use Return Value When:

✅ Computing properties bottom-up from children
✅ Result for parent depends ONLY on children’s results
✅ No need to compare across sibling branches
✅ Tree structure properties (height, diameter, balance)
✅ Can express as: result = combine(left_result, right_result)

Examples:

Tree height/depth
Sum of node values
Check if tree is balanced
Lowest common ancestor (with specific return encoding)

Use Both When:

✅ Need to track global optimum while computing local properties
✅ Different metrics at each level (global max vs local contribution)

Examples:

Maximum path sum (any path)
Diameter of tree (longest path between any two nodes)
Max difference between node and ancestor

Common Pitfalls & How to Avoid Them

Pitfall 1: Using Primitive Parameter as “Global” State (Java)

// ❌ WRONG: prev doesn't persist across calls
private void dfs(TreeNode node, int prev) {
    // ...
    prev = node.val;  // Only updates local copy!
    dfs(node.right, prev);
}

Fix: Use class-level variable or wrapper class:

// ✅ CORRECT: Use Integer[] or class field
private Integer prev = null;

// OR use array as mutable reference
private void dfs(TreeNode node, int[] prev) {
    prev[0] = node.val;  // Modifies array content
}

Pitfall 2: Over-Using Global Variables

// ❌ BAD: Using global for simple tree height
private int maxDepth = 0;

public int maxDepth(TreeNode root) {
    dfs(root, 0);
    return maxDepth;
}

private void dfs(TreeNode node, int depth) {
    if (node == null) {
        maxDepth = Math.max(maxDepth, depth);
        return;
    }
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
}

Fix: Use return value for cleaner code:

// ✅ BETTER: Return value is clearer
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Pitfall 3: Forgetting to Reset Global Variables

class Solution {
    private int count = 0;  // ❌ Persists across test cases!
    
    public int countNodes(TreeNode root) {
        dfs(root);
        return count;
    }
}

Fix: Always reset in the public method:

public int countNodes(TreeNode root) {
    count = 0;  // ✅ Reset before each call
    dfs(root);
    return count;
}

Interview Strategy: What Interviewers Expect

1. Ask Clarifying Questions

Before coding, state your approach:

“I notice this problem requires tracking the minimum across all nodes. I’ll use a class-level variable to accumulate results during DFS. Is that acceptable?“

2. Explain the Trade-off

When asked “Can you avoid the global variable?”:

If yes: Explain the alternative (return value pattern)
If no: Explain why (e.g., “We need to track state across sibling branches”)

3. Code Cleanly

Initialize global variables clearly
Add comments explaining what the return value represents
Name variables descriptively (prevNodeVal, not x)

4. Test Edge Cases

Empty tree (null root)
Single node
Skewed tree (all left or all right)
Negative values (if applicable)

Practice Problems

Global Variable Pattern

LC 98: Validate Binary Search Tree
LC 109: Convert Sorted List to BST ⭐ (Inorder simulation pattern)
LC 230: Kth Smallest Element in BST
LC 257: Binary Tree Paths
LC 129: Sum Root to Leaf Numbers

Return Value Pattern

Hybrid Pattern

Summary: Your Interview Cheat Sheet

Indicator	Use Global Variable	Use Return Value
State scope	Across entire tree	Within subtree only
Traversal order matters	✅ Yes (in-order, etc.)	❌ No
Compare siblings	✅ Yes	❌ No
Track “previous” node	✅ Yes	❌ No
Bottom-up computation	❌ No	✅ Yes
Tree property (height, sum)	❌ No	✅ Yes
Accumulate results	✅ Yes	Use return + combine

Final Tip for Interviews

When in doubt, start with return values (cleaner, easier to reason about). If you find yourself needing to “remember” something from a previous node or sibling branch, switch to global variable.

With these patterns mastered, you’ll confidently handle 80%+ of tree DFS problems in interviews! 🚀