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

Question

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?

trincot · Accepted Answer · 2022-08-23 10:25:12Z

2

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 Aug 23, 2022 at 10:25

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Scary Wombat · Accepted Answer · 2022-08-23 00:22:43Z

0

Another option would be not to have the recursive method return the list, but have the recursive method add to a list field.

private List<Integer> output;

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

}

answered Aug 23, 2022 at 0:22

Scary Wombat

44.9k6 gold badges38 silver badges67 bronze badges

3 Comments

PatPanda Over a year ago

This sounds interesting! Upvoting the idea. May I ask if you can share an example? And besides the example, is there a way to have the recursion + return as list?

Scary Wombat Over a year ago

well if you return, the list, you will need to either pass it to the recursive method, so that it can be added to, or to take two resulting lists and merge. Personally I would go for my answer and you do not need to change the methods signature.

PatPanda Over a year ago

Thanks a lot! I do wish to return something, hence having List<Integer> in the method signature, let me try to come up with something based on what you just said (if you have it handy, please share!)

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related