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

Question

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:

You tree is incorrect. It has the children of node `3` reversed. — beaker, Sep 24 '15 at 17:05
what about `4 3 5`? could be both a 'full' tree with 4 as root and 5,3 as nodes; and a branch 4-5-3. seems like some additional information is needed to arrive at a definitive answer. — yurib, Sep 24 '15 at 18:14
possible duplicate of [how to build a binary tree from preorder and inorder traversals](http://stackoverflow.com/questions/5213069/how-to-build-a-binary-tree-from-preorder-and-inorder-traversals) — dfeuer, Sep 24 '15 at 18:27
See also [How does inorder+preorder construct unique binary tree](http://stackoverflow.com/questions/30556590/how-does-inorderpreorder-construct-unique-binary-tree/30566218#30566218) — dfeuer, Sep 24 '15 at 18:31
Actually I didn't know preorder and inorder travarsal. Thanks for giving those links. — madMDT, Sep 25 '15 at 05:40
I don't think you always can correctly do this with BFS and DFS. Consider two binary trees containing nodes labeled 1, 2, 3. The first has 2 and 3 as children of 1. The second has 2 as a child of 1 and 3 as a child of 2. The BFS ordering for both *could be* 1, 2, 3. The DFS ordering for both *could be* 1, 2, 3. They would be indistinguishable by considering only the BFS and DFS traversals. — Patrick87, Sep 25 '15 at 19:29

score 6 · Accepted Answer · 2015-09-25T19:35:06.207

6

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)

edited Sep 25 '15 at 19:35

answered Sep 24 '15 at 21:59

what does the `allMatchingInOrder()` means in here: `int[] children_bfs = bfs.allMatchingInOrder(children_dfs)` ? – madMDT Sep 25 '15 at 17:58
1

@madMDT that "error" you corrected was no error, but following the mathematical notation, so `[x , y[` means range `x` to exclusively `y`. `allMatchingInOrder` is supposed to generate an array containing all values from the parameter in the order in which they appear in the array it's called on. So for example: `{0 , 1 , 2 , 3 , 4}.allMatchingInOrder({1 , 4 , 3})` would return `{1 , 3 , 4}`. The `subset()`-function is supposed to generate a subset starting at the index specified by the first parameter and ending at the index given by the second parameter (sry, theres actually a mistake here). – Sep 25 '15 at 18:55
if I take i in [1 , at [ in the rule 1 step then how can I take peers[i] it the same step? Looks like peers[0] will be missing! – madMDT Sep 25 '15 at 19:28
Could you explain what your algorithm would give if the BFS traversal is 1, 2, 3 and the DFS traversal is 1, 2, 3? I believe there are two unique trees here (maybe that's OK? OP doesn't say "generate the unique tree"). – Patrick87 Sep 25 '15 at 19:31
1

By the way, where did you pick up the [a, b[ notation for intervals? I've seen [a, b) more commonly. – Patrick87 Sep 25 '15 at 19:32
@madMDT oh, right, sry, my mistake. i've written this rather hasty. I'll correct that – Sep 25 '15 at 19:34
@Patrick87 for the notation: i've seen it at university (looked pretty plausible to me), though it might be the personal style of that prof. For the example: that's a corner-case that can't be solved. My algorithm would generate a tree with 1 as root and 2 and 3 as children of 1, since Rule 1 is applied first – Sep 25 '15 at 19:38
Generally the notation `[a,b)` is used to indicate the range where `a` is inclusive and `b` is exclusive. I think this should be standard notation as this is more widely used. – Mostafiz Rahman Sep 25 '15 at 19:44
I wonder - if you tried all combinations of applying rule #1 vs rule #2 in cases where both apply, would you get all possible trees that have the given traversals? If so, I'd discuss the existence & uniqueness problems in this answer and how your algorithm can solve the problem completely. +1 in any event. – Patrick87 Sep 25 '15 at 19:55
@Patrick87 there's only the corner-case where DFS and BFS are equal, which allows for multiple valid solutions. Since this algorithm is recursive, this aswell applies for subtrees. I'll update with a more complex algorithm that'll remove that flaw (atleast for subtrees). – Sep 26 '15 at 11:15
Damn, that's actually harder than i thought. I've been racking my brain quite some time now without coming up with anything better than some incomplete ideas – Sep 28 '15 at 07:28

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

1 Answers1

Linked