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
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhat 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
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.
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.