CODEWITHSUNDEEP
algorithmgraphdepth-first-searchbreadth-first-searchtree-traversal
madMDT
madMDT

Reputation: 458

How to construct a tree with it's BFS and DFS traversal

I have the BFS and DFS traversal of a tree. How can I reconstruct the tree from these traversals?

For example: 

BFS Traversal : 4 3 5 1 2 8 7 6

DFS Traversal : 4 3 1 7 2 6 5 8

then the tree would be like bellow:

       4
      / \
     3   5    
    / \   \    
   2   1   8
   |   |         
   6   7

Upvotes: 3

Views: 10939

Answers (1)

user4668606
user4668606

Reputation:

This is only possible if BFS and DFS use exactly the same order to traverse children:

Rule 1: 

BFS Traversal : 4 3 5 1 2 8 7 6
                | | |
                | | |-------|
                | |         |
DFS Traversal : 4|3 1 7 2 6|5 8

As this example shows, we can easily know that (3 , 1 , 7 , 2 , 6) belong to a subtree that has 3 as root. Since 1 is aswell part of that subtree, we can derive that 3 and 5 are the only children of 4.

Rule 2:

BFS Traversal : 4 3 5 1 2 8 7 6
                | |   |
                | | |-|
                | | |        
DFS Traversal : 4 3 1 7 2 6 5 8

This way, we can show that 3 and 5 are the children of 4.

This can aswell be done using only subsets of BFS and DFS that hold nodes that belong to the same subtree (this example is the subtree found in the demonstration of Rule 1):

Using Rule 1:

BFS Traversal: 1 2 7 6
               | |
               | |-|
               |   |
DFS Traversal: 1|7|2 6

This shows that 7 is the only child of 1.

Using Rule 2:

BFS Traversal: 1 2 7 6
               |   |
               | |-|
               | |  
DFS Traversal: 1 7 2 6

Thus 1 and 2 are children of the same parent (which would be 3).

Translated into pseudocode this would look like this:

addchild(int parent, int child) := add the child to the specified parent node

void process(int[] bfs , int[] dfs)
    int root = bfs[0]

    //find all peers (nodes with the same level and parent in the tree) using Rule 2
    int at = bfs.find(dfs[2])
    int peers[at - 1]
    for int i in [1 , at[
        peers[i - 1] = bfs[i]
        addchild(root , bfs[i])

    //for each of the childtree of the tree find it's children using Rule 1
    for int i in [0 , length(peers)[
        //all nodes that are either peers[i] or a child of peers[i]
        int[] children_dfs = dfs.subset(dfs.find(peers[i]) , (i < length(peers) - 1 ? dfs.find(peers[i + 1]) : length(dfs)) - 1)
        //a subset of bfs containing peers[i] and it's children in the order they have in bfs
        int[] children_bfs = bfs.allMatchingInOrder(children_dfs)

        //generate the subtree
        process(children_bfs , children_dfs)

Upvotes: 6

Related Questions