Populate inorder successor for all nodes Given a binary tree where each node has following structure, write a
  function to populate next pointer for all nodes. The next pointer for
  every node should be set to point to inorder successor.

struct node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
}

  
  Initially, all next pointers have NULL values. Your function should
  fill these next pointers so that they point to inorder successor.


This code is attributed to GeeksForGeeks. Looking for code review, optimizations and best practices.

public class PopulateInorderSuccessor&lt;T&gt; {

    private TreeNode&lt;T&gt; root;

    public PopulateInorderSuccessor(List&lt;T&gt; items) {
        create (items);
    }

    private void create(List&lt;T&gt; items) {
        if (items.size() == 0) {
            throw new IllegalArgumentException("There should atlease be single item in the tree");
        }

        root = new TreeNode&lt;&gt;(items.get(0));

        final Queue&lt;TreeNode&lt;T&gt;&gt; queue = new LinkedList&lt;TreeNode&lt;T&gt;&gt;();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i &lt; half; i++) {
            if (items.get(i) != null) {
                final TreeNode&lt;T&gt; current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNode&lt;T&gt;(items.get(left));
                    queue.add(current.left);
                }
                if (right &lt; items.size() &amp;&amp; items.get(right) != null) {
                    current.right = new TreeNode&lt;T&gt;(items.get(right));
                    queue.add(current.right);
                }
            }
        }
    }

    private static class TreeNode&lt;T&gt; {
        private TreeNode&lt;T&gt; left;
        private T item;
        private TreeNode&lt;T&gt; right;
        private TreeNode&lt;T&gt; next;

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

    private static class TreeNodeHolder&lt;T&gt; {
        private TreeNode&lt;T&gt; treeNode;
    }

    public void populateInorderSuccessor() {
        populate(root, new TreeNodeHolder&lt;T&gt;());
    }

    private void populate(TreeNode&lt;T&gt; node, TreeNodeHolder&lt;T&gt; treeNodeHolder) {
        if (node != null) {
            populate(node.right, treeNodeHolder);
            node.next = treeNodeHolder.treeNode;
            treeNodeHolder.treeNode = node;
            populate(node.left, treeNodeHolder);
        }
    }

    public List&lt;T&gt; toInOrderList() {
        TreeNode&lt;T&gt; node = root;

        while (node.left != null) {
            node = node.left;
        }

        final List&lt;T&gt; list = new ArrayList&lt;&gt;();
        while (node != null) {
            list.add(node.item);
            node = node.next;
        }
        return list;
    }
}


public class PopulateInorderSuccessorTest {

    @Test
    public void testCompleteTree() {
        PopulateInorderSuccessor&lt;Integer&gt; pis1 = new PopulateInorderSuccessor&lt;Integer&gt;(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        pis1.populateInorderSuccessor();        
        assertEquals(Arrays.asList(4, 2, 5, 1, 6, 3, 7), pis1.toInOrderList());
    }

    @Test
    public void testLeftSkewedTree() {
        // left skewed
        PopulateInorderSuccessor&lt;Integer&gt; pis2 = new PopulateInorderSuccessor&lt;Integer&gt;(Arrays.asList(1, 2, null, 4));
        pis2.populateInorderSuccessor();        
        assertEquals(Arrays.asList(4, 2, 1), pis2.toInOrderList());
    }

    @Test
    public void testRightSkewedTree() {
        // right skewed
        PopulateInorderSuccessor&lt;Integer&gt; pis3 = new PopulateInorderSuccessor&lt;Integer&gt;(Arrays.asList(1, null, 3, null, null, null, 7));
        pis3.populateInorderSuccessor();        
        assertEquals(Arrays.asList(1, 3, 7), pis3.toInOrderList());
    }
}
I think this equivalent, but simpler. It removes the need for the TreeNodeHolder class by returning a TreeNode&lt;T&gt;.

public void populateInorderSuccessor() {
  populate(root, null);
}

private TreeNode&lt;T&gt; populate(TreeNode&lt;T&gt; root, TreeNode&lt;T&gt; successor) {
  if (root == null) {
    return successor;
  }

  root.next = populate(root.right, successor);
  return populate(root.left, root);
}




PopulateInorderSuccessor is not a good name for a class. Let's change it to BinaryTree.



Tree construction can be simplified:

public BinaryTree(T[] items) {
  this.root = create(items, 0);
}

private TreeNode&lt;T&gt; create(T[] items, int i) {
  if (i &gt;= items.length || items[i] == null) {
    return null;
  }

  TreeNode&lt;T&gt; root = new TreeNode&lt;T&gt;(items[i]);
  root.left = create(items, 2 * i + 1);
  root.right = create(items, 2 * i + 2);
  return root;
}




I find that helper methods setLeft and setRight on TreeNode can make tree code a bit cleaner, in general. It's not of much advantage here, but just for reference:

public TreeNode&lt;T&gt; setLeft(TreeNode&lt;T&gt; left) {
  this.left = left;
  return this;
}

public TreeNode&lt;T&gt; setRight(TreeNode&lt;T&gt; right) {
  this.right = right;
  return this;
}


This way we can write

private TreeNode&lt;T&gt; create(T[] items, int i) {
  if (i &gt;= items.length || items[i] == null) {
    return null;
  }

  return new TreeNode&lt;T&gt;(items[i])
    .setLeft(create(items, 2 * i + 1))
    .setRight(create(items, 2 * i + 2));
}




Putting it all together, we get something like this

import java.util.ArrayList;
import java.util.List;

public class BinaryTree&lt;T&gt; {
  private TreeNode&lt;T&gt; root;

  public BinaryTree(T[] items) {
    this.root = create(items, 0);
  }

  private TreeNode&lt;T&gt; create(T[] items, int i) {
    if (i &gt;= items.length || items[i] == null) {
      return null;
    }

    return new TreeNode&lt;T&gt;(items[i])
      .setLeft(create(items, 2 * i + 1))
      .setRight(create(items, 2 * i + 2));
  }

  public void populateInorderSuccessor() {
    populate(root, null);
  }

  private TreeNode&lt;T&gt; populate(TreeNode&lt;T&gt; root, TreeNode&lt;T&gt; successor) {
    if (root == null) {
      return successor;
    }

    root.next = populate(root.right, successor);
    return populate(root.left, root);
  }

  public List&lt;T&gt; toInOrderList() {
    TreeNode&lt;T&gt; node = root;
    while (node.left != null) {
      node = node.left;
    }

    final List&lt;T&gt; list = new ArrayList&lt;&gt;();
    while (node != null) {
      list.add(node.item);
      node = node.next;
    }
    return list;
  }

  private static class TreeNode&lt;T&gt; {
    private TreeNode&lt;T&gt; left;
    private T item;
    private TreeNode&lt;T&gt; right;
    private TreeNode&lt;T&gt; next;

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

    public TreeNode&lt;T&gt; setLeft(TreeNode&lt;T&gt; left) {
      this.left = left;
      return this;
    }

    public TreeNode&lt;T&gt; setRight(TreeNode&lt;T&gt; right) {
      this.right = right;
      return this;
    }
  }
}