Converting a preorder traversal array to an level order traversal array (or vice versa) given that the binary tree was filled in Level Order

Question

Say you have a binary tree that was filled in level order, i.e. every level is filled before any of that level's node's children. Such a tree can be uniquely defined by it's level order traversal. For instance {1,2,3,4,5,6} is

    1
 2     3
4 5   6

A preorder traversal of this would produce the array {1,2,4,5,3,6}

Is there a way to convert one of these arrays to the other directly, that is faster than generating the actual tree and preforming the actual traversal on it? (for tree with n nodes)

Shihab Shahriar Khan Shihab Shahriar Khan · Accepted Answer · 2017-11-03T10:10:59

Yes, both of that is possible in a single pass.

First, level to pre-order, because that's a bit easier. Since this is a level-filled tree, for any node in array, given it's index i, the formula for index of left sub-tree's node is 2*i+1, for right it's, 2*i+2. So, we call them recursively in pre-order, appending root nodes into the back of our desired array.

def level_to_pre(arr,ind,new_arr):
    if ind>=len(arr): return new_arr #nodes at ind don't exist
    new_arr.append(arr[ind]) #append to back of the array
    new_arr = level_to_pre(arr,ind*2+1,new_arr) #recursive call to left
    new_arr = level_to_pre(arr,ind*2+2,new_arr) #recursive call to right
    return new_arr

And call it like this, here the last blank array will be populated.

ans  = level_to_pre([1,2,3,4,5,6],0,[])

Now before I go to the pre to level part, remember dfs uses recursion, which uses a stack behind the scene. Where as bfs uses queue. And the problem in our hand, populating array in level-first order, is basically bfs. So, instead of recursive calling (i.e stack), we will have to explicitly maintain a queue to emulate those recursive calls.

What we do here is, given root of a subtree, we add it to answer array first. Now, finding index of child nodes is challenging, unlike the problem above. Left one is easy, it'll be immediately after root. To find right's index, we calculate total size of left subtree. This is possible because we know it's level filled. We now use a helper function left_tree_size(n) that returns left subtree's size given the size of whole tree. So,apart from root's index, 2nd parameter we would be passing in case of recursion is size of this sub-tree. To reflect that, we put a (root,size) tuple in our queue.

from math import log2
import queue

def pre_to_level(arr):
    que = queue.Queue()
    que.put((0,len(arr)))
    ans = [] #this will be answer
    while not que.empty():
        iroot,size = que.get() #index of root and size of subtree
        if iroot>=len(arr) or size==0: continue ##nodes at iroot don't exist
        else : ans.append(arr[iroot]) #append to back of output array
        sz_of_left = left_tree_size(size) 
        que.put((iroot+1,sz_of_left)) #insert left sub-tree info to que
        que.put((iroot+1+sz_of_left,size-sz_of_left-1)) #right sub-tree info 

    return ans

And lastly, here is the helper function, follow a few examples to figure out why it works.

def left_tree_size(n):
    if n<=1: return 0
    l = int(log2(n+1)) #l = no of completely filled levels
    ans = 2**(l-1)
    last_level_nodes = min(n-2**l+1,ans)
    return ans + last_level_nodes -1

Converting a preorder traversal array to an level order traversal array (or vice versa) given that the binary tree was filled in Level Order

1 Answers