Binary Trees - Number of Nodes at a Level Let T be a binary tree. Write a O(n) -
ID: 3674108 • Letter: B
Question
Binary Trees - Number of Nodes at a Level Let T be a binary tree. Write a O(n) -time algorithm that receives as input a node n and an integer I and outputs the number of nodes that are at level I of the tree rooted at n. For example, in the figure shown below, if the inputs are node a and l = 1, then the algorithm should return 2, and if the input is node a and 1 = 2, the algorithm should return 3. If there are no nodes on level I, then the algorithm should return zero. For example, for the tree below, if the input is node a and l = 4, the algorithm should return zero. For node v, use v.left and v.,right to denote the left child and the right child of v, respectively, and v.parent to denote the parent of v. You cannot assume that each node knows on which level of the tree it is located, but you can store an additional variable at each node, namely v.varExplanation / Answer
int count(n,l)
return countUtil(n,0,l)
int countUtil(x,currentLevel,desiredLevel)
if currentLevel = desiredLevel
return 1
left = 0
right = 0
if x.left != null
left = countUtil(x.left, currentLevel+1, desiredLevel
if x.right != null
right = countUtil(x.right, currentLevel+1, desiredLevel
return left + right
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.