Python-Programs/Construct Tree Using Inorder and PostOrder.py at main · tasha06/Python-Programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
"""
-------------------------------  Construct Tree Using Inorder and PostOrder  ------------------------------

Given Postorder and Inorder traversal of a binary tree, create the binary tree associated with the
traversals.
You just need to construct the tree and return the root.

Note:
    Assume binary tree contains only unique elements.

#### Input format :
    Line 1 : n (Total number of nodes in binary tree)
    Line 2 : Post order traversal
    Line 3 : Inorder Traversal
#### Output Format :
    Elements are printed level wise, each level in new line (separated by space).

#### Sample Input :
    8
    8 4 5 2 6 7 3 1
    4 8 2 5 1 6 3 7
#### Sample Output :
    1
    2 3
    4 5 6 7
    8
"""

import queue
class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def buildTreePostOrder(postorder, inorder):

    if len(postorder)==0:
        return None
    root=BinaryTreeNode(postorder[-1])

    rootindex=-1
    for i in range(0,len(inorder)):
        if inorder[i]==root.data:
            rootindex=i
            break

    if rootindex==-1:
        return None

    leftinorder=inorder[0:rootindex]
    rightinorder=inorder[rootindex+1:]

    l=len(leftinorder)

    rightpostorder=postorder[l:len(postorder)-1]
    leftpostorder=postorder[:l]

    ltree=buildTreePostOrder(leftpostorder,leftinorder)
    rtree=buildTreePostOrder(rightpostorder,rightinorder)

    root.left=ltree
    root.right=rtree

    return root

def printLevelATNewLine(root):

    if root==None:
        return

    inputQ = queue.Queue()
    outputQ = queue.Queue()

    inputQ.put(root)

    while not inputQ.empty():

        while not inputQ.empty():

            curr = inputQ.get()

            print(curr.data, end=' ')
            if curr.left!=None:
                outputQ.put(curr.left)

            if curr.right!=None:
                outputQ.put(curr.right)
        print()
        inputQ, outputQ = outputQ, inputQ

# Main
n=int(input())
postOrder = [int(i) for i in input().strip().split()]
inorder = [int(i) for i in input().strip().split()]
root = buildTreePostOrder(postOrder, inorder)
printLevelATNewLine(root)