[FIXED] Java : binary tree + preorder traversal + recursion + return a result list

Issue

Small Java question on a preorder traversal of a binary tree, using recursion, with a result list of all the elements returned please.

Looking at the web we can see many result on the use of recursion to traverse a tree. However, they all "just print" the nodes, returning nothing:

https://makeinjava.com/recursive-binary-tree-traversal-algorithm-java-preorder-postorderinorder/

public static void preOrderRecursive(Node root) {
    if (null == root) {
        return;
    }
    System.out.printf("%d ", root.data);
    preOrderRecursive(root.left);
    preOrderRecursive(root.right);
}

This is a recursive function 👍 but does not return anything 👎

On the other hand, there are many examples where it returns the binary tree as list, but using an iterative way:

public List<Integer> preorderIterative(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.add(node.val);
      if (node.right != null) {
        stack.add(node.right);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
    }
    return output;
  }

This is an iterative function 👎, it does return the result as list 👍

My question is, I am having hard time building a recursive function 👍 which returns the result as list 👍.

What I tried (and not working):

 public static List<Integer> preOrderRecursiveWithReturn(TreeNode root) {
        if (null == root) {
            return ???;
        } else {
            return preOrderRecursiveWithReturn(root.left) preOrderRecursiveWithReturn(root.right) ???
        }
    }

But unfortunately, it is not working. Any help please?

Solution

Create a helper function that takes the output list as extra argument:

    // Helper
    private static void preOrderRecursive(Node root, LinkedList<Integer> output) {
        if (null == root) {
            return;
        }
        output.add(root.data);
        preOrderRecursive(root.left, output);
        preOrderRecursive(root.right, output);
    }

    // Actual function that returns the list
    public static LinkedList<Integer> preOrder(Node root) {
        LinkedList<Integer> output = new LinkedList<Integer>();
        preOrderRecursive(root, output);
        return output;
    }

Answered By - trincot
Answer Checked By - Marie Seifert (JavaFixing Admin)