A full trinary tree has no missing nodes, i.e., all interior nodes have three ch

Question

A full trinary tree has no missing nodes, i.e., all interior nodes have three children and all leaf nodes are at the same level as shown in these examples: Implement the generic isFullTriTree method below so that it returns true if the trinary tree is full, false otherwise. public static boolean isFullTriTree(TrinaryTreenode n) {//TODO: COMPLETE THIS METHOD} The method is passed a reference to a TrinaryTreenode that is the root of the tree. The TrinaryTreenode class is implemented as partially shown below: class TrinaryTreenode {//*** fields *** private T data; private TrinaryTrecnodc leftChild; private TrinaryTreenode midChild; private TrinaryTreenode rightChild;//*** methods *** public T getData() { return data;} public TrinaryTreenode getLeft() { return leftChild;} public TrinaryTreenode getMid() { return midChild;} public TrinaryTreenode getRight() { return rightChild;}}

Explanation / Answer

Code:

// function to calculate depth of the tree
public static int depth(TrinaryTreenode<T> n)
{
// if given node if
if(n == NULL)
return 0;
  
// otherwise
int l, m, r;
// get depths of 3 children of the node
l = depth(n->getLeft()) + 1;
m = depth(n->getMid()) + 1;
r = depth(n->getRight()) + 1;
  
// return the highest value as depth of that node
if(l > m)
{
if(l > n)
return l;
else
return n;
}
else
{
if(m > n)
return m;
else
return n;
}
}

// function to find if full
public static boolean isFullTriTree(TrinaryTreenode<T> n)
{
// return true id node is null
if(n == NULL)
return true;
  
// other wise, check if depth of all 3 children are same
if(depth(n->getLeft()) == depth(n->getMid()) && depth(n->getRight()) == depth(n->getMid()))
{
// if depth is same, then check if each child is a full tri tree
if(isFullTriTree(n->getLeft()) && isFullTriTree(n->getMid()) && isFullTriTree(n->getRight())
{
// if all chidren have same depth and all children are full tri trees
// then given tree is a Full Tri Tree
// so return true
return true;
}
}
// if any of above condition fails, return fasle
return false;

}

-------------------------------------------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.