How to construct a Binary Tree from Inorder and Postorder Traversal iteratively?

Question

Construct a Binary Tree from Inorder and Postorder Traversal iteratively.

I've seen how to do it with recursion, but I'm looking for an answer that constructs the binary tree iteratively.

I wrote an algorithm for inorder and preorder, but I'm wondering how to modify it for inorder and postorder?

Note: It's in pseudocode and "=" means "=="

Node:

e: TElement
right: PNode (pointer to a Node)
left: PNode (pointer to a Node)

Binary Tree:

root: PNode

Subalgorithm tree(preorder, inorder)

pre: preorder: Int[], inorder: Int[]

preOrderIndex<- 0;
inOrderIndex<-0;

Stack(s) 
root <- createNode(preorder[0])
push(s, root)

preOrderIndex<-preOrderIndex +1

While !empty(s)
    element(s, top) //which is the same as top = peak(s)
    
    if [top].e = inorder[inOrderIndex] 
        delete(s, top) //delete the element from the stack
        inOrderIndex<-inOrderIndex +1
    
        if inOrderIndex = length(inorder) 
            
            return root
        End if
        
        element(s, elem) 
        
        if !empty(s) and [elem].e = inorder[inOrderIndex]
            continue
        End if
        
       
        nod <- createNode(preorder[preOrderIndex])
        [top].right<-nod
        preOrderIndex<-preOrderIndex +1
        push(s,nod)
    Else
        nod <- createNode(preorder[preOrderIndex])
        [top].left<-nod
        preOrderIndex<-preOrderIndex +1
        push(s,nod)
    End if
End while

return root

End Subalgorithm

Edit: I've found the answer

"Edit: I've found the answer" -- what was it? If you add a self answer then you can contribute your knowledge to the community so that others with the same problem as you can benefit in the future. Thanks. — ggorlen

trincot trincot · Accepted Answer · 2021-07-03T10:38:48

When you have a working solution given preorder and inorder traversals, then you can use the following observations to turn it into a solution given postorder and inorder traversals:

The reverse of an inorder traversal is equal to the inorder traversal of the mirrored tree (where left and right are swapped)
The reverse of an postorder traversal is equal to the preorder traversal of the mirrored tree

So make the following changes to your working algorithm:

Rename pre to post everywhere it occurs in variable names
Initialise postOrderIndex and inOrderIndex with length(inorder)-1
Replace their incrementing statements with decrementing ones
Replace the exit condition with if inOrderIndex < 0
Replace left with right and vice versa

How to construct a Binary Tree from Inorder and Postorder Traversal iteratively?

1 Answers