At the moment I want to understand how to find all the connected nodes in the tree.

Here is an example code:

class Tree: def __init__(self, root, subtrees=None): self.root = root self.subtrees = subtrees[:] if subtrees else [] def con(self, v1, v2): # base cases if v1 and v2 is None: return [] elif self.root is None: return [] elif v1 == v2: return [v1] else: path = [] for subtree in self.subtrees: path += subtree.con(v1, v2) return path

How to recurse through all the elements of the tree? Because in my code only the branches pass, and because of this, the answer is in the form of an empty list. I can not figure out how to find nodes with the root.

Output should be of the kind:

t1 = Tree (2, [Tree (5)])

t2 = Tree (4, [Tree (6), Tree (7)])

t = Tree (1, [t1, t2])

print (t.con (5,4))

5, 2, 1, 4

  • 2
    Add an example of input data, how is the class initialized and what should be the output? - Igor Lavrynenko

1 answer 1

 class Tree: def __init__(self, root, subtrees=None): self.root = root self.subtrees = subtrees[:] if subtrees else [] def con(self, v1, v2, path = []): if (v1 is None and v2 is None) or (self.root is None): return [] elif v1 == v2: return [v1] elif self.root != v1 and self.root != v2: path.append(self.root); for sub in self.subtrees: sub.con(v1, v2, path) elif self.root == v1: path.append(v1) elif self.root == v2: path.append(v2) return path

Well, something like that (I'm sorry, I didn’t understand if the order of the elements is important to you, if anything, you can think about how to redo it).

The point is this: we start recursion from the root of the tree and go through all the subtrees, start recursion from them until we find the vertex we need, recording all the vertices in the path along the way.

This approach has an obvious minus: t.con(5, 1) will give out just 1

So let's change something:

 class Tree: parent = None def __init__(self, root, subtrees=None): self.root = root self.subtrees = subtrees[:] if subtrees else [] if subtrees: for sub in subtrees: sub.parent = self; def find(self, path = []): if self.root is None: return path else: if not (self.root in path): path.append(self.root) if self.parent: self.parent.find(path) def con(self, v1, v2, path = []): if (v1 is None and v2 is None) or (self.root is None): return [] elif v1 == v2: return [v1] elif self.root != v1 or self.root != v2: for sub in self.subtrees: sub.con(v1, v2, path) if self.root == v1: self.find(path) elif self.root == v2: self.find(path) return path

We will store the ancestor of each subtree. In recursion, we will first descend to the necessary roots, and from them we will launch another recursion to the very top, and it is the second recursion that will prescribe the path .

But even here there is a problem: t.con(5, 2) will display [5, 2, 1] instead of [5, 2] Therefore, I wrote this crutch:

 class Tree: parent = None def __init__(self, root, subtrees=None): self.root = root self.subtrees = subtrees[:] if subtrees else [] if subtrees: for sub in subtrees: sub.parent = self; def find(self, v1, v2, path = [], first = False): if self.root is None: return path else: if not (self.root in path): path.append(self.root) else: return path if self.parent and (self.root != v1 and self.root != v2 or first): self.parent.find(v1, v2, path) def con(self, v1, v2, path = [], par = False): if (v1 is None and v2 is None) or (self.root is None): return [] elif v1 == v2: return [v1] if self.root == v1: if par: self.find(v1, v2, path, True) if self.root != v1 or self.root != v2: for sub in self.subtrees: sub.con(v1, v2, path, True) else: if self.root != v1 or self.root != v2: for sub in self.subtrees: sub.con(v1, v2, path, False) self.find(v1, v2, path, True) elif self.root == v2: if par: self.find(v1, v2, path, True) if self.root != v1 or self.root != v2: for sub in self.subtrees: sub.con(v1, v2, path, True) else: if self.root != v1 or self.root != v2: for sub in self.subtrees: sub.con(v1, v2, path, False) self.find(v1, v2, path, True) elif self.root != v1 or self.root != v2: for sub in self.subtrees: sub.con(v1, v2, path, False) return path

I just need to run find from the top, which is deeper than the second (then we will not go too high to the root of the source tree) and I have no idea how to do this without such a crutch or global variable.

Maybe you can leave the crutch, but somehow mix the elements of the code and it will turn out to be more compact, but I have been writing this for almost 2 hours, perhaps the eye has blurred, sorry. I would be glad if someone corrected.

  • Thank you very much! Looks very entertaining. Still, with binary trees it is much easier to find all this. - User007 pm
  • You are welcome. I think there is a certain plus or minus "reference" solution better than mine, but I could not find any specific algorithms on this topic. - Vlad Sivirin 2:49 pm