Randomly combine two binary trees

Question

I'm working on a project about genetic algorithm, the gene is binary trees.

Now I need to recombine them, the method is to randomly select a node on the two trees, and then replace them.

For example:

Tree 1 and 2, select node C from 1 and node I from 2

   A           H
 B   C       I   J
D E F G     K L M N

After combination

   A
 B   I
D E K L

My node structure:

class Node():
    def __init__(self, element):
        self.element = element
        self.left = None
        self.right = None

My method to get random nodes, it will return a random node:

def getRandomNode(root):
        rootSize = treeCal.treeSize(root)
        leftSize = treeCal.treeSize(root.left) if root.left else 0
        rightSize = treeCal.treeSize(root.right) if root.right else 0
        if leftSize == rightSize == 0: 
            return root
        randNum = random.randint(1, rootSize)
        if randNum <= leftSize: 
            return treeCal.getRandomNode(root.left)
        elif randNum == leftSize + 1:
            return root
        else:
            return treeCal.getRandomNode(root.right)

The method I currently use, dad and mom are both the root of the tree, the first method will report an error (cannot assign to function call), the second method is useless:

def recombine(dad, mom):
        child = dad
        getRandomNode(child) = getRandomNode(mom)
        return child

def recombine(dad, mom):
        child = dad
        select = getRandomNode(child)
        select = getRandomNode(mom)
        return child

I have searched on Internet for a long time, but I can’t get the answer I want. Most of the answers are to insert the second tree into the end of the first tree, which does not meet my requirements.

user_4150746 · Answer

the function getRandomNode() will return a value which you're storing, the value inside the function gets replaced by the new value inside the function. Note that you're not making a change in the tree in any way. You can modify the recombine function to change one of the children of the random node.

def recombine(dad, mom):
    child = dad
    select = getRandomNode(child)
    select2 = getRandomNode(mom)
    if random.randint(0, 1) == 0:
        select.right = select2
    else:
        select.left = select2
    return child

Randomly combine two binary trees

1 Answers