Question

Python Explain Code

 

#Python program

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def findMaxDifference(root, diff=float('-inf')):
    if root is None:
        return float('inf'), diff

    leftVal, diff = findMaxDifference(root.left, diff)
    rightVal, diff = findMaxDifference(root.right, diff)

    currentDiff = root.key - min(leftVal, rightVal)

    diff = max(diff, currentDiff)

    return min(min(leftVal, rightVal), root.key), diff

root = TreeNode(6)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.right.left = TreeNode(2)
root.right.right = TreeNode(4)
root.right.left.left = TreeNode(1)
root.right.left.right = TreeNode(7)

print(findMaxDifference(root)[1])

Answer 1

Given program finds maximum difference between a Node and its Decendents in Binary tree.

This program solve the problem in linear time by processing the tree nodes in bottom up manner.
It visits left and right subtree before processing current tree node.

The function findMaxDifference() returns minimum value among all nodes in sub-tree rooted at it.

For a node, we get minimum value in left subtree and minimum value in right subtree .

And find the maximum difference for every node and if difference is more then maximum difference calculated so far, it update it.

#Tree Node class stores a Binary tree Node
class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

#This function finds maximum difference between a node and its descendants
def findMaxDifference(root, diff=float('-inf')):
    # if tree is empty return infinity
    if root is None:
        return float('inf'), diff

    #recursively called on left and right sub tree
    leftVal, diff = findMaxDifference(root.left, diff)
    rightVal, diff = findMaxDifference(root.right, diff)
  
    # find maximum difference between current node and its descendants
    currentDiff = root.key - min(leftVal, rightVal)

    # update the maximum difference
    diff = max(diff, currentDiff)
  
    # return minimum value among all nodes in sub-tree rooted at it
    return min(min(leftVal, rightVal), root.key), diff

root = TreeNode(6)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.right.left = TreeNode(2)
root.right.right = TreeNode(4)
root.right.left.left = TreeNode(1)
root.right.left.right = TreeNode(7)

print(findMaxDifference(root)[1])