I believe the space complexity is O(n) here, but I'm also storing everything in the lists, so I'm not sure.

I believe it is only O(n) because of the recursions, but because I'm storing everything in lists, maybe this requires more space?

**The algorithm just shows the right side view of the binary tree, so if there root = 5, root.left = 3, root.right = 4. Then right side view will be just [5, 4]. If there was not a root.right, then right side view would be [5, 3]**

**What is the space complexity of this code?**

**Code:**

```
import java.util.*;

public class TestingJavaCode {

    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        List<Integer> leftS = new ArrayList<>();

        if (root == null) return res;

        res.add(root.val);
        leftS.add(root.val);

        if (root.right != null) {
            for (int i : rightSideView(root.right)) {
                res.add(i);
            }
        }

        if (root.left != null) {
            for (int j : rightSideView(root.left)) {
                leftS.add(j);
            }
        }

        for (int k = 0; k < leftS.size(); k++) {
            if (k > res.size() - 1) res.add(leftS.get(k));
        }

        return res;

    }

    public static void main(String[] args) {
        TestingJavaCode c = new TestingJavaCode();
        TreeNode s4 = new TreeNode(1);
        s4.left = new TreeNode(2);
        s4.right = new TreeNode(3);
        s4.left.left = new TreeNode(4);
        s4.left.right = new TreeNode(5);
        // [1, 3, 5]
        System.out.println(c.rightSideView(s4).toString());
    }

}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

```