August 2, 2020 - construct binary tree from post order and inorder traversal lists - August 2, 2020 2:00 PM mock interview

ContructBinaryTreeFromPostOrderInOrderList.py

class TreeNode:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

def get_binary_tree(l, r, postorder):
    if not inorder[l:r]: return None
    
    root = TreeNode(postorder.pop()) # 3  - last one in stack, l, r value
    root_location = lookup_inorder_index[root.val] # 3: 1
    
    root.right = get_binary_tree(root_location + 1, r, postorder) # ([15, 20, 7],[9,15,7,20])
    root.left = get_binary_tree(l, root_location, postorder)
    return root

# if __name__ == '__main__':
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3] 

# building lookup table
lookup_inorder_index = {}
for i, n in enumerate(inorder): lookup_inorder_index[n] = i

print(get_binary_tree(0, len(inorder), postorder))



# 
# Given inorder and postorder traversal of a tree, construct the binary tree.
"""
[9,3,15,20,7]
 0 1  2  3 4
root_location: 1 (3), 3(20), 4(7)
get_binary_tree(0, 5, [9,15,7,20,3])
3->right = get_binary_tree(2, 5, [9,15,7,20])
3->left = get_binary_tree(0, 1, [9])
9->right = get_binary_tree(1, 1, )

            3
    /           \
   9             20
              /     \
             15      7
                    /   \
                 None       None
                 
                 
Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3] 
             -
in postorder it is hard for us to divide left and right subtree (it is impossible)
What we know is the rightmost element is the current_root node always...

# Algo
We pop the right most element as the current_root_node,
Then we look for current_root_node in inorder to look for left and right subtree elements


                     
if not inorder: return None

Return the following binary tree:
    
    
     3
    / \
    9 20
      / \
     15  7   

inorder: left-tree | root | right-tree
postorder: left-tree | right-tree | root

                            root (postorder)
                            /        \
leftpart of the inorder list        rightpart of the inorder list

base case for the recurrssion is inorder-traversal
if not inorder: return None
root = 3
righttree = get_binary_tree(inorder = [15,20,7], postorder = [9,15,7,20])  # 9 is 
righttree = get_binary_tree(inorder = [], postorder = [9,15,7])
lefttree = get_binary_tree(inorder = [], postorder = [9,15])
lefttree = get_binary_tree(inorder = [9], postorder = [9])

n = len(postorder)

len(postorder)

number: index -> to find the position in the inorder traversal
tc: n
sc: n + n

"""