Question: Let T be a binary tree. Write a O(n) -time algorithm that receives as input a node n and an integer l and outputs the

Let T be a binary tree. Write a O(n) -time algorithm that receives as input a node n and an integer l and outputs the number of nodes that are at level l 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 l = 2, the algorithm should return 3. If there are no nodes on level l, 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.var
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
