0

I want to build a tree from the leaves to the root. I have a list that gives me the leaves in the order they must be in the bottom of the tree: a->b->c->d->e->f->g
Buiding from the leaves to the root i want every inner node to have both a left and a right child .The inner nodes of the tree and the root will be empty nodes . Its possible to have a tree where some leaves are further from the root than others if the number of the leaves(items in list) is odd What is the most efficient way to do it?

Fenia
  • 9
  • 2
  • When you say you have "a list that gives you the leaves", do you mean a list that gives you *values that are held by* the leaves, or do you mean actual leaf objects? Also, what are the characteristics of the internal nodes supposed to be? – John Bollinger Sep 14 '15 at 16:12
  • What kind of efficiency are you interested in? Code size? Performance? Memory? – Šimon Tóth Sep 14 '15 at 16:12
  • You seem to be looking for a B-tree: https://en.wikipedia.org/wiki/B-tree – alk Sep 14 '15 at 16:21
  • Possible duplicate to: http://stackoverflow.com/q/32376/694576 – alk Sep 14 '15 at 16:24
  • the tree must be binary but for every left child there must be a right one thats why it must be built from the bottom to the root. The tree will be some kind of segment tree so the internal nodes will have information about the segment they represent. – Fenia Sep 14 '15 at 16:29
  • im looking for efficiency in performance – Fenia Sep 14 '15 at 16:30
  • and the list given is a path of the segments i mention above – Fenia Sep 14 '15 at 16:31
  • it's called "up tree". I'm assuming you're trying to implement union-find(aka disjoint sets) data structure? – ThunderWiring Sep 14 '15 at 16:47
  • I don't get your reasoning why the tree must be built from the bottom, but if every inner node shall have both a left and a right node then you need an even number of leaves. Also what size is that list? Do you want to modify the (structure of the) tree after building it? – Daniel Jour Sep 14 '15 at 17:10
  • I thought the tree must be built from the bottom because 1)the bottom leaves will be the only information i have in that stage of the program the other nodes will be empty 2) i want every node of the tree to have a "brother node" .if you can suggest anotherway to do it i will . The number of the bottom leaves will be a number lets say N and will not change later. – Fenia Sep 15 '15 at 11:09

0 Answers0