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