Question

Write the recursive function max_depth; it is passed a binary (any binary tree, not necessarily a binary search tree) and a value as arguments. It returns the maxim depth in the tree at which that value occurs. Note the root is depth 0; its children are at depth 1; its grandchildren are at depth 2, etc. Generally, if a parent is at depth d, its children are at depth d 1. In the binary tree below, max_depth(tree,1) returns 1, max_depth (tree,2) returns 3, max_depth (tree,3) returns 2. The value may appear at many depths. ..1

Answer 1

A python code was used in writing of the recursive function max_depth; and passed a binary (any binary tree, not necessarily a binary search tree) and a value as arguments.

Step-by-step explanation:

Solution

To solve this given question we make use of Python programming language.

Thus

THE CODE:

class BinaryTreeNode:

def __init__(self, value, left=None, right=None):

self.value = value

self.left = left

self.right = right

# recursive max_depth function implementation

def max_depth(tree, value):

if tree == None:

return -1

# recursive calls to this function

leftDepth = max_depth(tree.left, value)

rightDepth = max_depth(tree.right, value)

# return the maximum depth

if tree.value == value or leftDepth > -1 or rightDepth > -1:

return 1 + max(leftDepth, rightDepth)

else:

return max(leftDepth, rightDepth)

btn1 = BinaryTreeNode(2)

btn2 = BinaryTreeNode(3, None, btn1)

btn3 = BinaryTreeNode(3)

btn4 = BinaryTreeNode(3)

btn5 = BinaryTreeNode(2, btn2, btn3)

btn6 = BinaryTreeNode(1, btn4)

tree = BinaryTreeNode(3, btn5, btn6)

print('max_depth(tree, 1):',max_depth(tree, 1))

print('max_depth(tree, 2):',max_depth(tree, 2))

print('max_depth(tree, 3):',max_depth(tree, 3))

Note: Kindly find an attached copy of the Implementation of max_depth() function, Code to test the max_depth() function and the sample output below.