Recursion vs Iteration leetcode

1305. All Elements in Two Binary Search Trees

The following exercise consist in the comparison of iterative against recursive solutions base on a leetcode exercise level medium.

Problem:

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

• Each tree has at most 5000 nodes.
• Each node’s value is between [-10^5, 10^5].

Solution with iteration:

To solve this problem, we do a DFS and list each tree in order and form an order list. After that we just iterate through them and take their smallest value.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public List<Integer> treeToList(TreeNode root1){
        TreeNode current1=root1;
        List<Integer> result= new ArrayList<Integer>();
        if(root1 == null ){
            return result;
        }
        Stack<TreeNode> st1 = new Stack<TreeNode>();      
        while(current1 != null || !st1.isEmpty() ){
            while(current1 != null){
                st1.push(current1);
                current1=current1.left;
            }
            current1=st1.pop();
            result.add(current1.val);     
            current1=current1.right;
        }
        return result;
        
    }
    
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> result= new ArrayList<Integer>();
        List<Integer> tree1=treeToList(root1);
        List<Integer> tree2=treeToList(root2);
        while(!tree1.isEmpty() || !tree2.isEmpty() ){
            if(tree1.isEmpty() ){
                result.add(tree2.get(0)); tree2.remove(0);
            }else if(tree2.isEmpty() ){
                result.add(tree1.get(0)); tree1.remove(0);
            }else{
                if(tree1.get(0) > tree2.get(0)){
                    result.add(tree2.get(0)); tree2.remove(0);
                }else{
                    result.add(tree1.get(0)); tree1.remove(0);
                }
            }
        }
        return result;
    }
}

Result with iteration:

Runtime: 41 ms, faster than 5.20% of Java online submissions for All Elements in Two Binary Search Trees.
Memory Usage: 41.1 MB, less than 97.16% of Java online submissions for All Elements in Two Binary Search Trees.

Solution with recursion:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public void treeToList(TreeNode root1,List<Integer> tree1 ){
        if(root1 != null ){
            treeToList(root1.left, tree1);
            tree1.add(root1.val);
            treeToList(root1.right, tree1);              
        }        
    }
    
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> result= new ArrayList<Integer>();
        List<Integer> tree1= new ArrayList<Integer>();
        treeToList(root1,tree1);
        List<Integer> tree2= new ArrayList<Integer>();
        treeToList(root2,tree2);
        while(!tree1.isEmpty() || !tree2.isEmpty() ){
            if(tree1.isEmpty() ){
                result.add(tree2.get(0)); tree2.remove(0);
            }else if(tree2.isEmpty() ){
                result.add(tree1.get(0)); tree1.remove(0);
            }else{
                if(tree1.get(0) > tree2.get(0)){
                    result.add(tree2.get(0)); tree2.remove(0);
                }else{
                    result.add(tree1.get(0)); tree1.remove(0);
                }
            }
        }
        return result;
    }
}

Results with recursion:

Runtime: 33 ms, faster than 8.00% of Java online submissions for All Elements in Two Binary Search Trees.
Memory Usage: 41.6 MB, less than 89.67% of Java online submissions for All Elements in Two Binary Search Trees.

Using recursion we consumed relatively the same amount of memory plus stack size, but we obtained a faster solution.