scheme The height of a tree is defined as the maximum number of nodes on a path

Question

scheme

The height of a tree is defined as the maximum number of nodes on a path from the root to a leaf. Write a recursive function (height T), which returns the height of the tree T. The following example illustrates the use of this function:

> (height T) 4

Write a recursive function (postorder T), which returns the list of all elements in the tree T corresponding to a postorder traversal of the tree. The following example illustrates the use of this function: > (postorder T)

(1 9 8 5 17 25 22 13)

Explanation / Answer

class Node:

def __init__(self, data):
self.data = data
self.left = None
self.right = None

# Compute the "maxDepth" of a tree -- the number of nodes
# along the longest path from the root node down to the
# farthest leaf node
def maxDepth(node):
   if node is None:
       return 0 ;

   else :

       # Compute the depth of each subtree
       leftDepth = maxDepth(node.left)
       rightDepth = maxDepth(node.right)

       # Use the larger one
       if (leftDepth > rightDepth):
           return leftDepth+1
       else:
           return rightDepth+1

'''Defining the tree structure '''
root = Node(13)
root.left = Node(5)
root.right = Node(22)
root.left.left = Node(1)
root.left.right = Node(8)
root.left.right.right = Node(9)
root.right.left = Node(17)
root.right.right = Node(25)

print("Depth of the tree is: " , maxDepth(root))

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.