Interview question. Find n-th In-order traversal element with and without recursion

FindNthInTree.java

package org.sdo.algorythms;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created by dsemenov
 * Date: 12/7/16.
 */
public class FindNthInTree<D> {

  public static class Node<T> {
    private T data;
    private Node<T> left;
    private Node<T> right;

    public Node(T data, Node<T> left, Node<T> right){
         this.data = data;
         this.left = left;
         this.right = right;
    }
  }

  public static class Holder<T>{
      private T val;
      private int idx;
      Holder(T val, int idx){
        this.idx = idx;
        this.val = val;
      }
  }

  public D findElement(Node<D> root, int n){
      Holder<D> r = internal(root, n, new Holder<D>(null, -1));
      return r.val;
  }

  private Holder<D> internal(Node<D> root, int n, Holder<D> holder) {
    if(root == null) {
      return holder;
    }
    Holder<D> h = internal(root.left, n, holder);
    if(h.val != null) return  h;

    h.idx = h.idx + 1;
    if(h.idx == n){
      h.val = root.data;
      return h;
    }
    return internal(root.right, n, h);
  }

  public D findElementWORecursion(Node<D> root, int n){
    Deque<Node<D>> stack = new LinkedList<>();
    while (root != null){
      stack.push(root);
      root = root.left;
    }
    int cnt = 0;
    while(!stack.isEmpty()){
      Node<D> node = stack.pop();
      if(cnt++ == n){
        return node.data;
      }else{
        Node nn = node.right;
        while(nn != null){
          stack.push(nn);
          nn = nn.left;
        }
      }
    }
    return null;
  }
}