Find height of tree

height.py

"""
https://practice.geeksforgeeks.org/problems/height-of-binary-tree/1

- use recursion to find the height
- use max on left and right branch on every recursion (add 1 every iteration)
"""
def height(root):
    if root is None:
        return 0
    return 1 + max(height(root.left), height(root.right))

#{ 
#  Driver Code Starts
# Node Class    
class node:
    def __init__(self, val):
        self.data = val
        self.next = None
        
# Linked List Class
class Linked_List:
    def __init__(self):
        self.head = None

    def insert(self, val):
        if self.head == None:
            self.head = node(val)
        else:
            new_node = node(val)
            temp = self.head
            while(temp.next):
                temp=temp.next
            temp.next = new_node

def createList(arr, n):
    lis = Linked_List()
    for i in range(n):
        lis.insert(arr[i])
    return lis.head

if __name__=='__main__':
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = list(map(int, input().strip().split()))
        head = createList(arr, n)
        print(findMid(head).data)
        
# } Driver Code Ends