MHB How Can You Check if a Binary Tree Satisfies the Properties of a 2-3 Tree?

[evinda]

Hello! (Nerd)

I want to write an algorithm that checks if a binary tree has the properties of a $\text{ 2-3 tree }$.

The properties of the $\text{ 2-3 trees }$ are the following :

• All the leaves have the same depth and hold one or two elements.
  
• Each internal node:
  
  • either holds one element and has two children
  • or holds two elements and has three children
• The tree is sorted
  

How could we check if a binary tree satisfies the above properties? (Thinking)

 

[I like Serena]

Hello! (Nerd)

I want to write an algorithm that checks if a binary tree has the properties of a $\text{ 2-3 tree }$.

The properties of the $\text{ 2-3 trees }$ are the following :

• All the leaves have the same depth and hold one or two elements.
  
• Each internal node:
  
  • either holds one element and has two children
  • or holds two elements and has three children
• The tree is sorted
  

How could we check if a binary tree satisfies the above properties? (Thinking)

Hey! (Wave)

How about recursing through the tree?
What does the algorithm for such a recursion look like? (Wondering)

And at each node, check which of these conditions are applicable, and if they are, whether they are satisfied?
What are the checks that you should make to verify if each of the conditions apply, to start with? (Wondering)

 

[evinda]

Hey! (Wave)

How about recursing through the tree?
What does the algorithm for such a recursion look like? (Wondering)

And at each node, check which of these conditions are applicable, and if they are, whether they are satisfied?
What are the checks that you should make to verify if each of the conditions apply, to start with? (Wondering)

Does this algorithm maybe check if a binary tree satisfies the properties of a $\text{2-3 tree}$ ? (Thinking)

int Algorithm(R)
{
   int leftdepth,rightdepth;
   if(R==NULL)
      return -1;      
   leftdepth=Algorithm(R->left);
   rightdepth=Algorithm(R->right);
   if ((leftdepth==rightdepth) && (leftdepth != -2))
      return leftdepth+1;       
   else
      return -2;        
}

 

[I like Serena]

Does this algorithm maybe check if a binary tree satisfies the properties of a $\text{2-3 tree}$ ? (Thinking)

int Algorithm(R)
{
   int leftdepth,rightdepth;
   if(R==NULL)
      return -1;      
   leftdepth=Algorithm(R->left);
   rightdepth=Algorithm(R->right);
   if ((leftdepth==rightdepth) && (leftdepth != -2))
      return leftdepth+1;       
   else
      return -2;        
}

This returns the depth of the tree, or -2 if the leaves are not all on the same level.
Good! (Smile)

But... that is not enough, nor is it what the problem asked, is it? (Wasntme)