CODEWITHSUNDEEP
algorithmtreebinary-treebinary-search-treegraph-algorithm
lllllllllllll
lllllllllllll

Reputation: 9130

How to efficiently spawn a binary tree from certain nodes?

Not sure if it is a proper place to ask for such question.. But I will just post it anyway...

Suppose I have a binary tree, which certain nodes marked as red:

     n1
    /  \
   red n2
   / \  \
  n3 n4  red
         / \
        n5 n6

So what I would like to do, is for every red node, spawn the tree into two new trees, and put each of the child into one tree.

So for the above case, it would become four trees like this:

  n1
 / \
n3  n2
    /
   n5

  n1
 / \
 n4 n2
    /
   n5

  n1
 / \
n3  n2
     \
     n6

  n1
 / \
 n4 n2
     \
     n6

It seems a pretty clean-defined problem.. but so far I just cannot come up with a good solution for this..

Could anyone shed some lights on this problem? Thank you a lot!

Upvotes: 1

Views: 105

Answers (3)

danbanica
danbanica

Reputation: 3038

A few observations that can lead to a clean implementation:

  • if there are n red nodes, then there will be 2n trees (this ignores the situation where the red node is a leaf -- those probably don't matter and can be eliminated by a pre-processing step).
  • any number k between 0 and 2n - 1 can represent one configuration -- the decision taken at the ith red node (i.e. whether to keep the left or the right sub-tree) is indicated by the ith bit of k. This bit can be easily obtained using bit-wise operations, e.g. by comparing k & (1 << i) with 0.

The main function that can generate trees one by one would look like this:

void spawnAllTrees(baseTree) {
    int nRed = countRedNodes(baseTree);

    // this assigns to each red node an index between 0 and nRed - 1
    // (e.g. according to a pre-order tree traversal). 
    // it computes a hash map denoted as "redIndex" which
    // stores the mapping from Node to int
    computeRedIndices(baseTree);

    for (int k = 0; k < (1 << nRed); k++) {
        crtTree = spawnTree(baseTree, k);
    }
}

The code for spawnTree would be:

Node spawnTree(baseTreeNode, k) {
    if (baseTreeNode.isRed()) {
        idx = redIndex[baseTreeNode];
        if (!bitIsSet(k, idx)) {
            return spawnTree(baseTreeNode->left(), k);
        } else {
            return spawnTree(baseTreeNode->right(), k);
    } else {
        return new Node(baseTreeNode->value(), 
                        spawnTree(baseTreeNode->left(), k), 
                        spawnTree(baseTreeNode->right(), k));
    }
}

EDIT:

Changed the algorithm a little bit -- incrementing a counter to determine the current red node index is not valid. Different decisions at a certain red node could make another red node receive different indices for different configurations.

Upvotes: 2

Guy Coder
Guy Coder

Reputation: 24976

Since binary trees can be represented as linear expressions the binary tree

   n1
  /  \
 red n2
 / \  \
n3 n4  red
       / \
      n5 n6

can be represented as the linear expression ((n3 red n4) n1 (n2 (n5 red n6)))

Now a linear expression for a binary tree can be represented as a BNF and red can be replaced with an | or operator 

<s> ::= <a> n1 (n2 <b>)
<a> ::= n3 | n4
<b> ::= n5 | n6

Now all the possible combinations (walks) of this BNF are

n3 n1 (n2 n5)
n3 n1 (n2 n6)
n4 n1 (n2 n5)
n4 n1 (n2 n6)

and these can be turned back into the trees of your answer.

Upvotes: 2

Arvindsinc2
Arvindsinc2

Reputation: 716

Here is the algorithm:

node main_root_address; //address of very first node

function myfunc_inorder(root_address) //call this from main 
{
  if root_address is null return;

  myfunc_inorder(root_address->left);

  if(root_address->value is "red")
  {
    node temp = root_address;
    root_previous->parent = root_address->left;
    //inside each node along with value and pointer to left and right             subtree store the address of the parent node.
    myfunc_inorder(main_root_address);
    root_previous->parent = root_address->right;
    myfunc_inorder(main_root_address);
    root_address = temp;
  }

  myfunc_inorder(root_address->right);
}

How this algorithm is working?

First I will start with "node n1", then move to "node red" then to "node n3" then back to "node red"...Here I will replace "red" with left sub-tree and then with right sub-tree and repeat the algorithm until no red is left...

Upvotes: 1

Related Questions