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
}
Advertisement
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);
}