tree traversal result in a list-CodePudding

I have looked into tree traversal methods, but most of them use void modifiers and just printed the traversal sequence. Instead, is there a way to make a list of the sequence using recursion in Java? The starter code is below. Since preorder is List<T>, it should return a list, but global variables are not allowed. Then, there should be a list instance within the preorder method, but because it is recursive, the list will be created repetitively as well. I am stuck. Could someone versed in algorithm and Java help me with this?

public class Traversals<T extends Comparable<? super T>> { 
    //no global variables allowed
    public List<T> preorder(TreeNode<T> root) {
    // CODE HERE.
    }
}

public class TreeNode<T extends Comparable<? super T>> {

    private T data;
    private TreeNode<T> left;
    private TreeNode<T> right;

    TreeNode(T data) {
        this.data = data;
    }

    T getData() {
        return data;
    }

    TreeNode<T> getLeft() {
        return left;
    }

    TreeNode<T> getRight() {
        return right;
    }

    void setData(T data) {
        this.data = data;
    }

    void setLeft(TreeNode<T> left) {
        this.left = left;
    }

    void setRight(TreeNode<T> right) {
        this.right = right;
    }
}

i could do It iteratively, but I do not know how to do recursively.

CodePudding user response：

Using just the `preorder(TreeNode<T>)` method

This should also work and satifies all your contraints. A new list empty list is created every time and enriched with the list from the left and the right branch of the recursion.

public class Traversals<T extends Comparable<? super T>> {
    //no global variables allowed
    public List<TreeNode<T>> preorder(TreeNode<T> root) {
        var preorderLst = new LinkedList<TreeNode<T>>();
        if(root != null) {
            preorderLst.add(root);
            var leftList = preorder(root.getLeft());
            var rightList = preorder(root.getRight());
            preorderLst.addAll(leftList);
            preorderLst.addAll(rightList);
        }
        return preorderLst;
    }
}

Using a 2nd private method

Admittedly not the nicest solution but a simple working solution.

public class Traversals<T extends Comparable<? super T>> {
    //no global variables allowed
    public List<TreeNode<T>> preorder(TreeNode<T> root) {
        var preorderLst = new LinkedList<TreeNode<T>>();
        preorder(root, preorderLst);
        return preorderLst;
    }

    private void preorder(TreeNode<T> root, List<TreeNode<T>> preorderLst){
        if(root == null) return;
        preorderLst.add(root);
        preorder(root.getLeft(), preorderLst);
        preorder(root.getRight(), preorderLst);
    }
}

If you just need the data for a List<T> you would just need to call .getData() when adding root to the list.

Using just the preorder(TreeNode<T>) method

Using a 2nd private method

Using just the `preorder(TreeNode<T>)` method