CODEWITHSUNDEEP
c++data-structurestreemultiway-tree
Bramble
Bramble

Reputation: 1395

Finding the height of a multiway tree

How do you find the height of a multi-way tree? If I wanted to find the height of a binary tree, I could do something like this:

int height(node *root) {
  if (root == NULL)
    return 0;
  else
    return max(height(root->left), height(root->right)) + 1;
}

But I am not sure if I can apply a similar recursive method to a multiway tree.

Upvotes: 2

Views: 2791

Answers (5)

Jonathan Leffler
Jonathan Leffler

Reputation: 755044

Isn't it '1 + maximum height of sub-tree starting from any of the child nodes of the (current) root node'?

Note that the binary tree is just a special case of the multi-way tree where the child nodes are known to be the left child and the right child. The result is zero if the root node pointer is null.

Upvotes: 0

jjnguy
jjnguy

Reputation: 138972

The general case would be:

int height(node *root)
{
    if (root == NULL)
        return 0;
    else {
        // pseudo code
        int max = 0;
        for each child {
            int height = height(child);
            if (height > max) max = height;
        }
        return max + 1;
    }
}

Upvotes: 4

Daniel Spiewak
Daniel Spiewak

Reputation: 55123

For what it's worth (almost nothing), this problem renders beautifully in pure-functional languages like SML:

fun height Node(children) = (foldl max -1 (map height children)) + 1

Upvotes: 1

JaredPar
JaredPar

Reputation: 755477

This depends on how the child nodes are stored. Lets assume for a second that they are stored in a vector. You could then use the following to calculate their height. 

int height(node* root ) {
  if ( !root ) {
    return 0;
  }
  int max = 0;
  for ( vector<node*>::const_iterator it = root->children.begin();
        it != root->children.end();
        it++ ) {
    int cur = height(*it);
    if ( cur > max ) {  
      max = cur;
    }
  }
  return max+1;
}

Upvotes: 1

Jason S
Jason S

Reputation: 189876

if non-null:

  • find the height of each of the children
  • take the maximum
  • add 1

Upvotes: 0

Related Questions