Search code examples
treebinary-treepseudocode

How to insert Binary tree to array

I tried to write pseudo code to take a binary tree and insert it into an array according to Level order (aka Breadth first) traversal.

What I tried to write:

InsertToArray(Node *T):
    First, Create new Arr[size of the tree], Create S Queue
    Push(S,T)
    For i=0 to Len(Arr) do:
        IF 2*I smaller than Len(Array):
            Temp=Pop(S)
            Arr[i]=Temp
            Arr[2i]=Temp.Left
            Arr[2i+1]=Temp.Right
            IF T.Left isn’t NULL then Push(S,T.Left)
            IF T.Right isn’t NULL then Push(S,T.Right)
        Else IF 2*I larger than Len(Array): break the loop

I don't think it's correct code, I don't really know how to write it.

Solution

  • Since you do not mention the tree is a complete binary tree, the way you handle array index makes no sense here.

    One easy way is to do a regular level-order traversal and append the current element to the array.