CODEWITHSUNDEEP
algorithmrecursiontreeiterationbinary-tree
aneys
aneys

Reputation: 73

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

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

Upvotes: 1

Views: 517

Answers (1)

trincot
trincot

Reputation: 350137

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

Upvotes: 1

Related Questions