1
$\begingroup$

What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?

Example:

      15
    /    \
   10     5
  /  \   / \
 2    8 1   4
$\endgroup$
  • $\begingroup$ What makes you think there is a name for it? The great thing about language is that it lets us describe and name things for ourselves -- there are many more good ideas than existing "names", and there's no reason to think that every good idea has to have a standard "name". $\endgroup$ – D.W. Jul 18 '18 at 18:14
  • $\begingroup$ Maybe someone studied this before and gave a name, I just wanted to know if there is a name. If I know how people call it I can search it on web and study it. $\endgroup$ – ferit Jul 18 '18 at 18:14
  • $\begingroup$ My standard advice is: figure out what you'd do with the "name", and then ask about that. If the name would help you research this to answer some question about the data structure, then ask that question. That way either someone responds with a name, or answers your question. But I don't find questions of the form "here is my data structure/algorithm, does it have a name?" very likely to be valuable to others in the future. $\endgroup$ – D.W. Jul 18 '18 at 18:16
  • $\begingroup$ This looks like some type of Binary Tree but if you're asking for a specific condition where the descending nodes are equal to it's preceding node, then I don't think that has a specific name for that. $\endgroup$ – KingDuken Jul 18 '18 at 20:43
  • $\begingroup$ Such trees are encountered in dynamic huffman/arithmetic coders. Never seen specific name for them though $\endgroup$ – Bulat Jul 24 '18 at 11:05
2
$\begingroup$

It is called a SumTree. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.

$\endgroup$
  • $\begingroup$ Do you have a source for this? If so, it would help to provide a link or citation to the source that proposed/introduced this terminology. (I've never heard of the term "SumTree" before.) $\endgroup$ – D.W. Jul 19 '18 at 15:20
  • $\begingroup$ @D.W. I dont have exact online source for this. This was taught in my university. But if you google it you will find some good source. Here is one Check here $\endgroup$ – Kalana Mihiranga Jul 19 '18 at 16:43
  • $\begingroup$ That looks like a web page that defines its own term. I'm still not convinced this is a standard term that most people will have heard of or that is accepted among the community. $\endgroup$ – D.W. Jul 19 '18 at 16:58
0
$\begingroup$

Like others have pointed out there is no name for it but it looks like a Binary Search Tree or a version of it AVL or WBT that is augmented.

$\endgroup$
  • 2
    $\begingroup$ The example given specifically isn't a BST, and any version of this structure with positive weights can never be a BST. $\endgroup$ – Draconis Jul 19 '18 at 0:00
  • $\begingroup$ lol I went full retard your right some of the nodes on the right are lower than its parent $\endgroup$ – Venkada Narasiman Jul 19 '18 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.