recursion - Sorted Singly Linked List to BST Java -

i have sorted linked list, , void return method, need recursively construct balanced binary search tree list (which referred second parameter). , parameters can have ll head, root being created, , length of list.

the method cannot destructive ll, , test tree afterwards have printtree , treedepth:

public static void makebalancedtree(listnode head, treenode root, int count) {     //here } public static void printtree(treenode root) {     if(root != null)     {          //print recursive left, center, recursive right         printtree(root.left);         system.out.print(root.data + " ");         printtree(root.right);     }    }  public static int depth(treenode root) {     if (root == null)         return -1;      int deep;     //return larger of 2 subtree's depths, +1     deep = math.max(depth(root.right), depth(root.left));     return deep+1;     } public static int countlist(listnode head)     {          int count = 0;          listnode cursor = new listnode();         cursor = head;          while (cursor.link != null)         {             cursor = cursor.link;             ++count;         }         return count;      } 

you specified java, i'm not going write homework solution here's working solution in ruby.

class treebuilder   attr_reader :root    # generate root instance var , getters    # constructor.  tree empty.   def initialize     @root = nil   end    # public front-end building binary tree   # iterable set.  invokes recursive back-end.     def buildtree(alist)     alist.sort!      # ensure list sorted, delete if trust input     # hand recursive end iterator , initial list size,     # make returned result root of tree.     @root = __build_tree__(alist.each, alist.size)   end    # autocreate node class structure payload ,   # left , right subtree references.  automagically has   # setters , getters same name instance vars.       node = struct.new(:payload, :left, :right)    # recursive end attempts build subtrees.   # takes enumerator (iterator if prefer)   # linked list, current depth of attempt (which   # how balance maintained), , returns node reference.       def __build_tree__(list_enum, depth)     if depth > 0      # if we're not deep in tree balance...       # try constructing left subtree first       left = __build_tree__(list_enum, depth / 2)       # current node...       # begin/rescue block corresponds java if/else check       # on whether iterator "hasnext()".  java can pre-check,       # ruby says "just try getting next value , catch       # exception if it's not there"       begin         # try getting next value linked list         value = list_enum.next       rescue stopiteration         # if ran out of values, bail out "left" subtree         return left       end       # if succeeded in getting value, construct node store       # in, populate left subtree, , try building , populating       # right subtree well.       return node.new(value, left, __build_tree__(list_enum, (depth-1) / 2))     end     # recursive base case - if kept going, tree end unbalanced     return nil   end end 

as said above, actual working code in ruby. it's map assignment, contains basic logic iterate through list , put each element in appropriate location end balanced tree.