Binary search tree with insertion order maintained

Problem

Design a binary search tree where the insertion order is maintained.

Solution

In the binary tree in each node maintains a next pointer which acts as a linked list through the nodes which maintain insertion order. There would be normal left and right pointer which maintains the property of the binary search tree. The tree will provide an additional method called getSortedOrder, which returns a list of elements in insertion order. After inserting every node we will add that new node to the linked list's last node and advance the last pointer to the next node. So any time we can insert a node in BST in O(log n) time and in O(1) we can add it to the linked list. If the BST allows deletion then to maintain the linked list in O(1) time we need a doubly linked list.

Code

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

public class BinaryTreeInsertionOrder
{
 public static void main(String[] args)
 {
  BinaryTree bt = new BinaryTree();
  bt.add(4).add(5).add(2).add(9).add(14).add(6).add(3);
  List < integer > list = bt.getSortedOrder();
  for (Integer num : list)
   System.out.print(num + ", ");
  System.out.println();
  list = bt.getInsertionOrder();
  for (Integer num : list)
   System.out.print(num + ", ");
  System.out.println();
 }

 private static class BinaryTree
 {
  Node root;
  Node head;
  Node last;

  public BinaryTree add(int num)
  {
   if (root == null)
   {
    root = new Node(num);
    head = root;
    last = root;
   } else
   {
    Node node = new Node(num);
    add(root, node);
    last.next = node;
    last = node;
   }
   return this;
  }

  private void add(Node root, Node node)
  {
   if (node.value < root.value)
   {
    if (root.left == null)
     root.left = node;
    else
     add(root.left, node);
   } else
   {
    if (root.right == null)
     root.right = node;
    else
     add(root.right, node);
   }

  }

  public List < integer > getInsertionOrder()
  {
   Node current = head;
   List < integer > list = new ArrayList < integer >();
   while (current != null)
   {
    list.add(current.value);
    current = current.next;
   }
   return list;
  }

  public List < integer > getSortedOrder()
  {
   List < integer > list = new ArrayList < integer >();
   inorder(root, list);
   return list;
  }

  private void inorder(Node root, List < integer > list)
  {
   if (root == null)
    return;
   inorder(root.left, list);
   list.add(root.value);
   inorder(root.right, list);
  }

 }

 private static class Node
 {
  int value;
  Node left;
  Node right;
  Node next;

  public Node(int value)
  {
   this.value = value;
  }

 }
}

Index