Find largest subtree having identical left and right subtrees in Python

Suppose we have a binary tree; we have to find the largest subtree having identical left and right subtree. Preferred time complexity is O(n).

So, if the input is like

then the output will be

To solve this, we will follow these steps −

• Define a function solve() . This will take root, encode, maxSize, maxNode

• if root is None, then

  • return 0

• left_list := list with a blank string

• right_list := list with a blank string

• ls := solve(root.left, left_list, maxSize, maxNode)

• rs := solve(root.right, right_list, maxSize, maxNode)

• size := ls + rs + 1

• if left_list[0] is same as right_list[0], then

  • if size > maxSize[0], then

    • maxSize[0] := size

    • maxNode[0] := root

• encode[0] := encode[0] concatenate "|" concatenate left_list[0] concatenate "|"

• encode[0] := encode[0] concatenate "|" concatenate str(root.data) concatenate "|"

• encode[0] := encode[0] concatenate "|" concatenate right_list[0] concatenate "|"

• return size

• From the main method, do the following −

• maximum := [0]

• encode := list with a blank string

• solve(node, encode, maximum, maxNode)

• return maximum

Example

Let us see the following implementation to get better understanding −

 Live Demo

class TreeNode:    def __init__(self, data):       self.data = data       self.left = self.right = None def solve(root, encode, maxSize, maxNode):    if (root == None):       return 0    left_list = [""]    right_list = [""]    ls = solve(root.left, left_list, maxSize, maxNode)    rs = solve(root.right, right_list, maxSize, maxNode)    size = ls + rs + 1    if (left_list[0] == right_list[0]):       if (size > maxSize[0]):          maxSize[0] = size          maxNode[0] = root    encode[0] = encode[0] + "|" + left_list[0] + "|"    encode[0] = encode[0] + "|" + str(root.data) + "|"    encode[0] = encode[0] + "|" + right_list[0] + "|"    return size def largestSubtree(node, maxNode):    maximum = [0]    encode = [""]    solve(node, encode, maximum,maxNode)    return maximum root = TreeNode(55) root.left = TreeNode(15) root.right = TreeNode(70) root.left.left = TreeNode(10) root.left.right = TreeNode(25) root.right.left = TreeNode(75) root.right.left.left = TreeNode(65) root.right.left.right = TreeNode(80) root.right.right = TreeNode(75) root.right.right.left = TreeNode(65) root.right.right.right = TreeNode(80) maxNode = [None] maximum = largestSubtree(root, maxNode) print("Root of largest sub-tree",maxNode[0].data) print("and its size is ", maximum)

Input

root = TreeNode(55) root.left = TreeNode(15) root.right = TreeNode(70) root.left.left = TreeNode(10) root.left.right = TreeNode(25) root.right.left = TreeNode(75) root.right.left.left = TreeNode(65) root.right.left.right = TreeNode(80) root.right.right = TreeNode(75) root.right.right.left = TreeNode(65) root.right.right.right = TreeNode(80)

Output

Root of largest sub-tree 70 and its size is [7]