Rooted tree impossible constructs

In summary, the task is to construct a rooted tree with specific constraints, including a maximum depth and maximum degree for each node. The goal is to determine the maximum number of nodes possible using a summation formula. However, there is a statement that if it is not possible to construct the tree, -1 should be printed. The question remains as to what conditions would lead to this outcome.
  • #1
spaghetti3451
1,344
33

Homework Statement



For a UVa problem, I am working on constructing a rooted tree with the following constraints.

1. A tree of depth D means that the tree should contain at least 1 node which is exactly D distance away from the root and there is no node of more than D distance from the root.

2. The degree of a node of the tree cannot be greater than V . Degree of a node is simply measured by the number of nodes it is directly connected to, via a single edge.

Homework Equations



The Attempt at a Solution



The goal is to determine the maximum possible number of nodes. To find that, I am looking to sum over all V^i , where i ranges from 0 to D. This summation appears to give the maximum number of nodes correctly in many cases, so I'm assuming it's correct.

However, the question also states that 'If it is not possible to construct the tree, print -1'. I can think of no possible case where this might occur. Do you think this is supposed to be be printed when the user enters V and D outside the range given in the problem.
 
Physics news on Phys.org
  • #2
V=0? Negative values? Non-integer values?
The full problem statement would help.
 

Related to Rooted tree impossible constructs

1. What is a rooted tree impossible construct?

A rooted tree impossible construct is a type of data structure in computer science that represents hierarchical relationships between data elements. It consists of nodes connected by edges, with one node designated as the root and all other nodes having a parent node. The term "impossible construct" refers to a specific type of rooted tree that cannot exist due to certain constraints or rules.

2. What are the constraints that make a rooted tree impossible construct?

There are a few different constraints that can make a rooted tree impossible construct. One common constraint is the requirement that all nodes in a rooted tree must have a single parent, except for the root which has no parent. If a node has more than one parent, it would create a cycle in the tree, making it impossible to represent as a rooted tree. Other constraints may involve the number of children a node can have, or the direction of edges in the tree.

3. How are rooted tree impossible constructs useful?

While the term "impossible construct" may sound negative, understanding these constraints and limitations can actually be very useful in computer science. It allows us to define and analyze different types of data structures and algorithms, and helps us identify and avoid potential problems or errors when designing and implementing these structures in software.

4. Can a rooted tree impossible construct be converted into a different type of data structure?

Yes, in some cases a rooted tree impossible construct can be converted into a different type of data structure that does not have the same constraints. For example, a rooted tree with multiple parents can be converted into a directed acyclic graph (DAG), which allows for nodes to have multiple parents. However, this conversion may not always be possible or practical, and may result in a loss of information or functionality.

5. How can I learn more about rooted tree impossible constructs?

If you are interested in learning more about rooted tree impossible constructs, there are many resources available online such as textbooks, research papers, and online courses. You can also consult with a computer science expert or join online communities and forums to discuss and learn more about this topic. Additionally, exploring and experimenting with different data structures and algorithms can also help deepen your understanding of rooted tree impossible constructs.

Similar threads

Comp Sci Number of trees in a Fibonacci Heap without CASCADING-CUT
    • Engineering and Comp Sci Homework Help
Replies
11
Views
1K
Algorithm for computing the depths of all the nodes of tree
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
I How do leaf nodes behave in regression decision trees?
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
951
C: Stack with binary search trees
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Finding a Local Minimum in a Complete Binary Tree with Log(N) Probes
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Delete 'F', 'E', 'V' from 2-3 Tree
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Proving the Number of Leaves is One More Than Internal Nodes in Binary Trees
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Comp Sci Working with classes and vectors in C++
    • Engineering and Comp Sci Homework Help
Replies
15
Views
1K
Comp Sci Validating Braces Placement for Expression Evaluation
    • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
C: Print specific fields from a structure
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top