Main.java

package com.company;

import java.util.*;
import java.util.concurrent.TimeUnit;

public class Main {
    private int n = 100000;
    private int depth = 0;
    private int maxStackSize = 0;
    private int currStackSize = 0;
    private List<TreeItem> recursionBypass = new ArrayList<TreeItem>();
    private List<TreeItem> stackBypass = new ArrayList<TreeItem>();
    private List<TreeItem> stack2Bypass = new ArrayList<TreeItem>();

    public int getDepth() {
        return depth;
    }

    public List<TreeItem> getRecursionBypass() {
        return recursionBypass;
    }

    public List<TreeItem> getStackBypass() {
        return stackBypass;
    }

    public List<TreeItem> getStack2Bypass() {
        return stack2Bypass;
    }

    private void growTree(TreeItem root) {
        Deque<TreeItem> stack = new ArrayDeque<TreeItem>();
        stack.push(root);
        for (int i = 0; i < n; i++) {
            TreeItem newItem = new TreeItem(i);
            if (i % 15 != 0 && stack.size() > 0) {
                stack.pop();
            }
            stack.peek().getChildren().add(newItem);
            stack.push(newItem);
            depth = Math.max(depth, stack.size());
        }
    }

    TreeItem findRecursion(TreeItem item, Object obj) {
        maxStackSize = Math.max(maxStackSize, currStackSize);
        recursionBypass.add(item);
        if (Objects.equals(item.getData(), obj)) {
            return item;
        }
        for (TreeItem child : item.getChildren()) {
            currStackSize++;
            TreeItem data = findRecursion(child, obj);
            currStackSize--;
            if (data != null) {
                return data;
            }
        }
        return null;
    }

    TreeItem findStack(TreeItem root, Object obj) {
        maxStackSize = 0;
        Deque<TreeItem> stack = new ArrayDeque<TreeItem>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeItem item = stack.pop();
            stackBypass.add(item);
            if (Objects.equals(item.getData(), obj)) {
                return item;
            }
            for (TreeItem child : item.getChildren()) {
                stack.push(child);
                maxStackSize = Math.max(maxStackSize, stack.size());
            }
        }
        return null;
    }

    TreeItem findStack2(TreeItem root, Object obj) {
        maxStackSize = 0;
        Deque<Iterator<TreeItem>> stack = new ArrayDeque<Iterator<TreeItem>>();
        stack.push(Collections.singletonList(root).iterator());
        while (!stack.isEmpty()) {
            Iterator<TreeItem> it = stack.peek();
            if (it.hasNext()) {
                TreeItem item = it.next();
                stack2Bypass.add(item);
                if (Objects.equals(item.getData(), obj)) {
                    return item;
                }
                stack.push(item.getChildren().iterator());
                maxStackSize = Math.max(maxStackSize, stack.size());
            } else {
                stack.pop();
            }
        }
        return null;
    }

    public static void main(String[] args) {
        TreeItem root = new TreeItem(0);
        Main main = new Main();
        main.growTree(root);
        System.out.println("Depth is " + main.getDepth());
        TimeWatch timer = TimeWatch.start();
        int numberToFind = main.getN() / 2;
        Object obj = main.findRecursion(root, numberToFind);
        System.out.println("Time of recursion search is " +
                timer.time(TimeUnit.MILLISECONDS) +
                ". Object: " + Objects.toString(obj, "Not found.") + "Max stack size is " + main.getMaxStackSize());


        timer.reset();
        obj = main.findStack(root, numberToFind);
        System.out.println("Time of stack search is " +
                timer.time(TimeUnit.MILLISECONDS) +
                ". Object: " + Objects.toString(obj, "Not found.") + "Max stack size is " + main.getMaxStackSize());

        timer.reset();
        obj = main.findStack2(root, numberToFind);
        System.out.println("Time of stack2 search is " +
                timer.time(TimeUnit.MILLISECONDS) +
                ". Object: " + Objects.toString(obj, "Not found.") + "Max stack size is " + main.getMaxStackSize());
        System.out.println(main.getRecursionBypass().equals(main.getStackBypass()));
        System.out.println(main.getRecursionBypass().equals(main.getStack2Bypass()));


    }

    public int getN() {
        return n;
    }

    public int getMaxStackSize() {
        return maxStackSize;
    }
}

class TreeItem {
    private Object data;
    private ArrayList<TreeItem> children;

    public TreeItem(int n) {
        data = n;
        children = new ArrayList<TreeItem>();
    }

    public Object getData() {
        return data;
    }

    public ArrayList<TreeItem> getChildren() {
        return children;
    }
}

class TimeWatch {

    long starts;

    public static TimeWatch start() {
        return new TimeWatch();
    }

    private TimeWatch() {
        reset();
    }

    public TimeWatch reset() {
        starts = System.currentTimeMillis();
        return this;
    }

    public long time() {
        long ends = System.currentTimeMillis();
        return ends - starts;
    }

    public long time(TimeUnit unit) {
        return unit.convert(time(), TimeUnit.MILLISECONDS);
    }

}