Iam_Sandeep

Construct Tree from Inorder & Preorder

Mar 12th, 2022
1,040
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.27 KB | None | 0 0
  1. #User function Template for python3
  2. link="https://practice.geeksforgeeks.org/problems/construct-tree-1/1"
  3.  
  4. class Solution:
  5.     def buildtree(self, inorder, preorder, n):
  6.        def help(inorder,preorder):
  7.             if not inorder and not preorder:return None
  8.             mid=inorder.index(preorder[0])
  9.             t=Node(preorder[0])
  10.             #skipping first element in preorder(root) and skipping the element at pos mid(root)
  11.             t.left=help(inorder[:mid],preorder[1:mid+1])
  12.             t.right=help(inorder[mid+1:],preorder[mid+1:])
  13.             return t
  14.        return help(inorder,preorder)
  15.  
  16.  
  17.  
  18. #{
  19. #  Driver Code Starts
  20. #Initial Template for Python 3
  21.  
  22. class Node:
  23.     def __init__(self,val):
  24.         self.data = val
  25.         self.right = None
  26.         self.left = None
  27.  
  28. def printPostorder(n):
  29.     if n is None:
  30.         return
  31.     printPostorder(n.left)
  32.     printPostorder(n.right)
  33.     print(n.data, end=' ')
  34.  
  35. if __name__=="__main__":
  36.     t = int(input())
  37.     for _ in range(t):
  38.         n = int(input())
  39.         inorder = [ int(x) for x in input().split() ]
  40.         preorder = [ int(x) for x in input().split() ]
  41.        
  42.         root = Solution().buildtree(inorder, preorder, n)
  43.         printPostorder(root)
  44.         print()
  45.  
  46. # } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment