Skip to content

Using an outer field only for one method

I am implementing a recursive in-order traversal for a binary tree and want to save the data for each node in a list inOrderList which is modified only by this method. defining the list in the inOrder function is a problem because it is recursive. not sure where to declare the list, maybe I should change the structure of the project, how should I implement this functionality with best practices?

class TreeNode {

    private TreeNode left;
    private TreeNode right;
    private Integer data;

    public TreeNode(TreeNode left, TreeNode right, Integer data) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    // getters..

}
class TreeOperations {

    public static void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.getLeft());
        inOrderList.add(node.getData()); // where to define ArrayList<Integer> inOrderList?
        inOrder(node.getRight());
    }

    // many more methods not using inOrderList

}

Answer

Have a helper function which does the actual recursion, i.e.:

public static List<Integer> inOrder(TreeNode node) {
    final List<Integer> inOrderList = new ArrayList<Integer>();
    inOrderHelper(node, inOrderList);
    return inOrderList;
}

private static void inOrderHelper(TreeNode node, List<Integer> inOrderList) {
    if (node == null) return;
    inOrderHelper(node.getLeft(), inOrderList);
    inOrderList.add(node.getData());
    inOrderHelper(node.getRight(), inOrderList);
}