In Java Language Write in pseudocode an algorithm that receives as input the roo
ID: 3937565 • Letter: I
Question
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!
Explanation / Answer
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.