CODEWITHSUNDEEP
pythontreebinary-tree
exilednick
exilednick

Reputation: 101

Construction of binary tree by applying functions on parent

I have a given number 'X'. I have two functions f(x) and g(x). Now I want to construct a binary tree with X as the parent node and f(X) as the left child and g(X) as the right child and continue this process on all child nodes and terminate if I find an element which is equal to X in both the child sub trees. How can I implement this?

Upvotes: 0

Views: 149

Answers (1)

mettleap
mettleap

Reputation: 1410

You can try doing it in this manner (this is just a pseudocode, not literal syntax):

public boolean myFunc(int x){
    // BFS on left subtree ///////////////////////////////////
    boolean ltreeContainsX = false;
    int dx = f(x); // f should be defined somewhere
    if(dx == x){
        ltreeContainsX = true;
    }else{
        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
    q.push(dx);
    while(q.size()!=0){
        int val = q.pop();
        int fval = f(val);
        q.push(fval);
        if(fval == x){
            lTreeContainsX = true;
            break;
        }
        int gval = g(val);
        q.push(gval);
        if(gval == x){
            lTreeContainsX = true;
            break;
        }
    }
    }
    // BFS on right subtree ///////////////////////////////////
    // ... do the same as the above code snippet, but this time,
    // you will push g(x) to an empty queue first and then proceed
    // find the boolean value called rtreeContainsX

    return ltreeContainsX && rtreeContainsX;
}

Upvotes: 1

Related Questions