11. When dealing with trees, algorithm complexity is usually measured in terms of the number of...

 

Transcribed Image Text:

11. When dealing with trees, algorithm complexity is usually measured in terms of the number of nodes in the tree while the elementary operation is usually a node traversal. Let T be a tree such that each node u has a parent, rightChild and leftChild. (a) 15 points Design and analyze an algorithm (provide pseudocode) that, given a node u in T determines its depth d. Analyze your algorithm. (b) 15 points Design and analyze an algorithm (provide pseudocode) that, given an integer d and a tree T with nodes u₁,..., un determines the number of nodes in T at depth d. 11. When dealing with trees, algorithm complexity is usually measured in terms of the number of nodes in the tree while the elementary operation is usually a node traversal. Let T be a tree such that each node u has a parent, rightChild and leftChild. (a) 15 points Design and analyze an algorithm (provide pseudocode) that, given a node u in T determines its depth d. Analyze your algorithm. (b) 15 points Design and analyze an algorithm (provide pseudocode) that, given an integer d and a tree T with nodes u₁,..., un determines the number of nodes in T at depth d.

Answer rating: 100% (QA)

a Algorithm to Determine Depth of a Node in Tree Algorithm DepthOfNodeu Input Node u in tree T Outpu... View the full answer