Python Program to Find the Largest value in a Tree using Inorder Traversal

When it is required to find the largest value in a tree using in order traversal, a binary tree class is created with methods to set the root element, perform in order traversal using recursion and so on.

An instance of the class is created, and it can be used to access the methods.

Below is the demonstration of the same −

Example

 Live Demo

class BinaryTree_Struct:    def __init__(self, key=None):       self.key = key       self.left = None       self.right = None    def set_root(self, key):       self.key = key    def inorder_traversal_largest(self):       largest = []       self.inorder_largest_helper_fun(largest)       return largest[0]    def inorder_largest_helper_fun(self, largest):       if self.left is not None:          self.left.inorder_largest_helper_fun(largest)       if largest == []:          largest.append(self.key)       elif largest[0] < self.key:          largest[0] = self.key       if self.right is not None:          self.right.inorder_largest_helper_fun(largest)    def insert_to_left(self, new_node):       self.left = new_node    def insert_to_right(self, new_node):       self.right = new_node    def search_elem(self, key):       if self.key == key:          return self       if self.left is not None:          temp = self.left.search_elem(key)       if temp is not None:          return temp       if self.right is not None:          temp = self.right.search_elem(key)          return temp       return None my_instance = None print('Menu (this assumes no duplicate keys)') print('insert <data> at root') print('insert <data> left of <data>') print('insert <data> right of <data>') print('largest') print('quit') while True:    my_input = input('What operation would you do ? ').split()    operation = my_input[0].strip().lower()    if operation == 'insert':       data = int(my_input[1])       new_node = BinaryTree_Struct(data)       suboperation = my_input[2].strip().lower()       if suboperation == 'at':          my_instance = new_node       else:          position = my_input[4].strip().lower()          key = int(position)          ref_node = None          if my_instance is not None:             ref_node = my_instance.search_elem(key)          if ref_node is None:             print('No such key exists')             continue          if suboperation == 'left':             ref_node.insert_to_left(new_node)          elif suboperation == 'right':             ref_node.insert_to_right(new_node)    elif operation == 'largest':       if my_instance is None:          print('The tree is empty')       else:          print('The largest element is : {}'.format(my_instance.inorder_traversal_largest()))    elif operation == 'quit':       break

Output

Menu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> largest quit What operation would you do ? insert 8 at root What operation would you do ? insert 9 left of 8 What operation would you do ? insert 4 right of 8 What operation would you do ? largest The largest element is : 9 What operation would you do ? > Use quit() or Ctrl-D (i.e. EOF) to exit

Explanation

• The ‘BinaryTree_struct’ class with required attributes is created.

• It has an ‘init’ function that is used to set the left and right nodes to ‘None’.

• It has a ‘set_root’ method that helps set the root of the binary tree.

• Another method named ‘inorder_traversal_largest’ that performs inorder traversal using recursion.

• Hence it has a helper function defined alongside.

• Another method named ‘insert_to_right’ is defined that helps add element to the right side of the root node.

• A method named ‘insert_to_left’ is defined, that helps add element to the left side of the root node.

• A method named ‘search_elem’ is defined, that helps search for a specific element.

• An object of the ‘BinaryTree_struct’ class is created.

• The user input is taken for the operation that needs to be performed.

• Depending on the user’ choice, the operation is performed.

• Relevant output is displayed on the console.