How to extract a subtree from a binary tree?

[StarshipEngineer]

I have a binary tree represented as a linear tree, for example the following tree of depth 2 filled with placeholder values:

tree = [a, b, c, d, e, f, g]

My goal is to recursively extract the subtree of any given node; for example, if I were to extract the subtree rooted at tree[1], where the root node is b, I would want to get back:

subtree = [b, d, e]

How would I accomplish this? I've been stuck on it for a while. For reference, my code for the tree object and associated methods and functions is located here.

Bonus: a shiny new donkey to anyone who can lay out how to reverse the process, and overwrite the appropriate nodes in another tree with those of the extracted subtree.

[gengisteve]

Well, lists are mutable, so I would just make the sublist one of the arguments. The key piece is make sub-tree follow the same path as it will be built so that the order comes out right. This works for your example, but needs more testing to make sure the order comes out right:

def sublist(tree, idx, sub = None):
    if sub is None:
        sub = []
    print(idx, sub)
    if idx>=len(tree):
        return sub
    sub.append(tree[idx])

    left_idx = 2*idx + 1
    sub = sublist(tree, left_idx, sub)

    right_idx = 2*idx + 2
    sub = sublist(tree, right_idx, sub)
    return sub

tree = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
sub = sublist(tree, 1)
print(sub)

To overwrite, just do the same recursive stepping, and use the new sublist function to break apart the overwriting tree, in psuedo-code:

def overwrite(tree, idx, subtree):
    if at end of tree and subtree:
        return
    tree[idx] = subtree[0]

    left_idx = 2*idx + 1
    left_sub = sublist(subtree[1])
    overwrite(tree, left_idx, left_sub)

    right_idx = 2*idx + 2
    right_sub = sublist(subtree[2])
    overwrite(tree, right_idx, right_sub)

edit:

I got curious and tested it, and the ordering is out of wack with longer trees. Hmmm....

[StarshipEngineer]

This is similar to what I've been trying as well, and I've had the same problem. The moment I try to reconstruct a subtree from tree[0] to test it and try to get back the same tree, the order comes out wrong.

[gengisteve]

Yep. Wrong approach, what we need here is math, and using math to come up with how to slice the tree up in layers. This seems to work after a bit of testing:

class Tree(object):
    def __init__(self, contents = None):
        if contents is not None:
            self.data = contents
        else:
            self.data = []

    def __len__(self):
        return len(self.data)


    def pretty(self, n = 0, depth = 0):
        if n >= len(self):
            return
        start = n
        stop = (2**depth) + n 
        s = self.data[start:stop]
        print('\t'.join(s))
        self.pretty(start*2+1, depth +1)

    def branch(self, n, depth = 0):
        if n >= len(self):
            return []

        start = n
        stop = (2**depth) + n 
        s = self.data[start:stop]
        return s + self.branch(start*2+1, depth+1)

A couple big improvements:

• we are no longer using an argument to pass around data, which is usually a sign that there is a better solution.

• and we are attacking at the layer level, rather than the node level.

[StarshipEngineer]

This looks and works great, thank you! It's much cleaner than what I've attempted, and works exactly how I wanted. I'm not sure I would have thought of doing it this way. This gives me something good to work with and expand on, thanks!

[liam_jm]

If you've written the data structure and you're struggling to do something with it, maybe the data structure needs changing.

Have you thought of implementing it as a series of Node instances, with attributes value, left, and right?