What is wrong with my Preorder traversal?

Question

I am trying to solve this problem https://oj.leetcode.com/problems/binary-tree-preorder-traversal/ , i.e. preorder traversal with recursive slution.

EDIT: The whole code:

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }
     static List<Integer> res = new ArrayList<Integer>();
     public List<Integer> preorderTraversal(TreeNode root) {
            if(root == null){
                return new ArrayList<Integer>();
            }
            res.add(root.val);
            if(root.left != null){
                res.add(preorderTraversal(root.left));
            }
            if(root.right != null){
                res.add(preorderTraversal(root.right));
            }
            return res;
      }
}

I have wrong answer because of the following:

Input:  {1,2}
Output:     [1,1,2]
Expected:   [1,2]

Can someone tell me how to fix this?

EDIT: I dont have main() method or unit tests. If you open the link that I posted you will see that this is online judging system.

Answer 1

The problem is that within each recursive loop, you are adding the entire array again into your final result.

For example, given the following tree:

  1
 /
2

Your first iteration adds 1 into 'res' variable. The problem is when it gets to this line:

res.add(preorderTraversal(root.left));

Then it recursively calls itself for the left side. That preorderTraversal will return the res array, which will be [1,2]. Hence, when [1,2] gets added to res (which was [1], remember?), then you get [1,1,2].

Here's code that should work:

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();

    if(root == null){
        return result;
    }

    result.add(root.val);
    if(root.left != null){
        result.addAll(preorderTraversal(root.left));
    }
    if(root.right != null){
        result.addAll(preorderTraversal(root.right));
    }

    return result;
}

Answer 2

For the left and right nodes, just call preorderTraversal recursively, and it will add the values to res. Calling add/addAll on res with the results of these recursive calls is wrong.

public class Solution {
     List<Integer> res = new ArrayList<Integer>();
     public List<Integer> preorderTraversal(TreeNode root) {
            if(root == null){
                return new ArrayList<Integer>();
            }
            res.add(root.val);
            if(root.left != null){
                preorderTraversal(root.left);
            }
            if(root.right != null){
                preorderTraversal(root.right);
            }
            return res;
      }
}

There's a little problem with this solution -- res retains the values from previous calls, so calling preorderTraversal more than once on the same instance may return incorrect results. Here's a solution that does not have this drawback:

public class Solution {
     public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            preorderTraversal(root, res);
            return res;
      }
      private void preorderTraversal(TreeNode node, List<Integer> res) {
          if (node != null) {
              res.add(node.val);
              preorderTraversal(node.left, res);
              preorderTraversal(node.right, res);
          }
      }
}

Answer 3

try this method code:

public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        res.add(root.val);
        if(root.left != null){
            res = preorderTraversal(root.left);
        }
        if(root.right != null){
            res = preorderTraversal(root.right);
        }
        return res;
   }

btw, you were doing res.add in the recursion. You should rather do res= in it.

Answer 4

A working solution :

import java.util.ArrayList;
import java.util.List;



class TreeNode 
{
      int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) 
    {
       ArrayList<Integer> res = new ArrayList<Integer>();

        if(root == null)
            return res;
        else res.add(root.val);

        if(root.left != null)
        {
            res.add(root.left.val);
            preorderTraversal(root.left);
        }

        if(root.right != null)
        {
            res.add(root.right.val);
            preorderTraversal(root.right);
        }


        return res;    
    }
}

public class TreeTest
{


    public static void main(String[] args)
    {

        Solution c = new Solution();

        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);

        //Link the nodes of the tree
        t1.left = t2;
        t1.right = t3;


        List<Integer> list = c.preorderTraversal(t1);

        System.out.println(list);
    }
}

Answer 5

Since you have not posted the whole code how the input is done and output is produced it is difficult to tell. For preorder traversal it should be something like this.

 void traverse(TreeNode node){
   if(node != null){
      res.add(node.val);
      traverse(root.left);
      traverse(root.right);
    }
}

Answer 6

public ArrayList<E> getPreOrderTraversal() {
    return getPreOrderTraversal(root);
}

private ArrayList<E> getPreOrderTraversal(Node tree) {
    ArrayList<E> list = new ArrayList<E>();

    if (tree != null) {
        list.add((E) tree.value);
        list.addAll(getPreOrderTraversal(tree.left));
        list.addAll(getPreOrderTraversal(tree.right));
    }

    return list;
}

Answer 7

A working and LeetCode accepted solution:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return preOrderTraversalInternal(root, list);
    }
    private List<Integer> preOrderTraversalInternal(TreeNode root, List<Integer> list){
    if(root == null) return list;
    list.add(root.val);
    if(root.left != null){
      preOrderTraversalInternal(root.left, list);
    }
    if(root.right != null){
      preOrderTraversalInternal(root.right, list);
    }
    return list;
  }
}

Answer 8

The problem is that within each recursive loop, you are adding the entire array again into your final result. You need to add left or right nodes only one time while traversing but in your code whole arr is getting added to the new res array. This result will contain repetitive nodes.

For these issues, please use Print statements after every recursive call to debug the problem.

Solution - Use addAll method: res.addAll(node.left);