Given a tree traversal order find out whether it is preorder inorder or postorder

Question

Assuming that someone gives me a tree traversal order for the nodes from A to G - F, B, A, D, C, E, G, I, H which can be either preorder, inorder or postorder

1. How can I determine whether its preorder, inorder or postorder efficiently?
2. How do I reconstruct the tree efficiently without having to construct the tree for each of the three traversal types like the one shown below?

Answer 1

Assuming the tree traversal given to you is accurate--

if you do not have any info on "what kind of tree", there's no way you can tell what kind of traversal it is.

if you are given info about the tree and how the values are organized, you possibly can.

if it is a binary tree, and if:

• the list is perfectly ordered, it is definitely in in-order

• the list is not ordered and some value which is not minimum in the list is the first value, it is definitely in pre-order (that first value is the root)

• the list isn't ordered and the first value is minimum. it is definitely in post-order.

Given the traversal of a binary tree,

if in-order : there is more than one tree that results in that in-order traversal .

if pre-order: exactly one tree corresponding to it (the first in a list is always the root of that subtree, the values less than root are in left-subtree and greater than are on the right)

if post-order: exactly one subtree (similar to pre-order above. )

Answer 2

binary tree node

class BTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

split tree to left and right subtree by root (pre[0])

def split_tree(pre, ino):
    l_ino, l_pre, r_ino, r_pre = None, None, None, None
    iri = None # in-order root index

    for i in range(len(ino)):
        if ino[i] == pre[0]:
            iri = ino[i-1]
            l_ino = ino[:i]
            r_ino = ino[i+1:]
            break
    for i in range(len(pre)):
        if iri == pre[i]:
            r_pre = pre[i+1:]
            l_pre = pre[1:i+1]
            break

    return (l_ino, l_pre, r_ino, r_pre)

construct binary tree

by getting pre-order and in-order traversal listes

def construct_bt(pre, ino):
    if len(ino) != len(pre):
        print('Error ino and pre is not match')
        return 
    
    if len(ino) == 0:
        return
    
    l_ino, l_pre, r_ino, r_pre = split_tree(pre, ino)

    root = BTNode(pre[0])
    root.left = construct_bt(l_pre, l_ino)
    root.right = construct_bt(r_pre, r_ino)

    return root

sample pre-order and in-order traversal

pre = [1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7]
ino = [8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7]

# root of binary tree 
root = construct_bt(pre, ino)