What is the minimum possible depth of a dry tree in dray tree each noods has at the most d children
Answers
Answer:
This is the Answer
Explanation:
I think you mean the minimum height of a d-ary tree with ‘m’ nodes.
Just the minimum height is -1 (for an empty tree) followed by 0 (for a tree with only root node).
For a tree with ‘m’ nodes, the minimum height is calculated as follows:
For finding minimum depth, we have to assume that all the possible positions in each level but the last are filled, i.e all nodes but the leaf nodes have m children.
In other words, you are trying to cram as many nodes in the top as possible without having to go down, and only start a new level when the current level is fully filled.
at level 0, we can only have 1 root node.
at level 1, we can have at most ‘d’ nodes which is the maximum number of children the root node can have.
at level 2, each of the ‘d’ nodes in level one can have ‘d’ children each, making maximum number of nodes in this level d^2.
level 3, each of the d^2 nodes can have d children each making maximum number of nodes here d^3.
Answer:
The minimum possible depth of a d-ary tree is Ω (log n / log d) where n is the number of nodes in the tree and d is the maximum number of children a node can have. The height of the tree is equal to the maximum depth of the tree.