In Java Language Write in pseudocode an algorithm that recei

In Java Language

Write in pseudocode an algorithm that receives as input the root of a tree and it returns true if the tree is a proper binary tree (i.e. each internal node has 2 children) and false otherwise. Assume that r.children is the number of children of a node r.

Compute the time complexity of the above algorithm in the worst case as a function of the number n of nodes and give its order.

Explain what the worst case for the algorithm is and how you computed the time complexity.

Thank you!

Solution

PLease find PSUDO CODE.

Use any tree traversal algorithm to visit each node, and return false if any node en-route has more than two children.

boolean isBinary(Node root) {

return isBinary(root)
}

private boolean isBinary(Node n) {

if (n has no child)
return true
elif (n has 1 child)
return isBinary(n.children[0])
elif (n has 2 children)
return isBinary(n.children[0]) && isBinary(n.children[1])
else
return false
}

struct Node {
children: List
}

TIme complexity: O(number_of_node), since we are traversing all nodes of tree