Styjun

In "def same_child_values". I am trying to compare two trees to see if the other tree has same value nodes to the primary tree.children. In this case I am using a set to compare them. But in my code when the tree depth is greater than 1 then my code cannot add the nodes into the set correctly. Can anyone help me?

class Tree:
 '''Tree ADT; nodes may have any number of children'''

 def __init__(self: 'Tree',
 item: object =None, children: list =None):
 '''Create a node with item and any number of children'''

 self.item = item
 if not children:
 self.children = []
 else:
 self.children = children[:]

 def __repr__(self: 'Tree') -> str:
 '''Return representation of Tree as a string'''

 if self.children:
 return 'Tree(0, 1)'.format(repr(self.item), repr(self.children))
 else:
 return 'Tree()'.format(repr(self.item))

 def is_leaf(self: 'Tree') -> bool:
 '''Return True iff this Tree node is a leaf (has no children).'''

 return self.children == []

 def remove_equal(self: 'Tree') -> None:
 '''Remove every child that has the same item as its parent;
 any children of a removed node n become children of an ancestor of n.

 >>> t = Tree(1, [Tree(2, [Tree(1), Tree(2)]), Tree(1)])
 >>> t.remove_equal()
 >>> repr(t)
 'Tree(1, [Tree(2, [Tree(1)])])'
 >>> t = Tree(4, [Tree(4, [Tree(6)])]) 
 >>> t.remove_equal()
 >>> repr(t)
 'Tree(4, [Tree(6)])'
 >>> t = Tree(4, [Tree(4, [Tree(4, [Tree(4)])])])
 >>> t.remove_equal()
 >>> repr(t)
 'Tree(4)'
 >>> t = Tree(4, [Tree(4, [Tree(4, [Tree(6), Tree(7)]), Tree(8)]), Tree(9)])
 >>> t.remove_equal()
 >>> repr(t)
 'Tree(4, [Tree(6), Tree(7), Tree(8), Tree(9)])'
 '''
 new_children = []
 for c in self.children:
 c.remove_equal()
 if not c.item == self.item:
 new_children.append(c)
 else:
 new_children.extend(c.children)
 self.children = new_children



 # Q1: Complete this method (This was the last part of last week's lab.
 # If you did not have a chance to finish it last week, work on it today.)

This is the function I need to finish

 def same_child_values(self: 'Tree', other: 'Tree') -> None:
 '''
 Return True iff the other tree node given has all the same values for its children.
 The values do not have to occur the same number of times.
 We are only looking at values of the immediate children, not the descendants.

 Hint: Use sets to compare a list of all children keys
 More on sets - https://www.programiz.com/python-programming/set

 >>> t = Tree(4, [Tree(6), Tree(7), Tree(8), Tree(9)])
 >>> t2 = Tree(5, [Tree(6), Tree(7, [Tree(8, [Tree(9)])])])
 >>> t3 = Tree(6, [Tree(7), Tree(8), Tree(6), Tree(6), Tree(9)])
 >>> t4 = Tree(7, [Tree(7), Tree(7), Tree(6)])
 >>> t.same_child_values(t2)
 False
 >>> t.same_child_values(t3)
 True
 >>> t4.same_child_values(t2)
 True
 '''
 a = set()
 b = set()

This is my code:

 for c in self.children:
 a.add(c.item)
 c.same_child_values(other)
 for d in other.children:
 b.add(d.item)
 self.same_child_values(d)
 return b

if my "other" tree is t3 I expect to see in my set()

my set() = 8, 9, 6, 7

if my "other" tree is t2 I expect to see in my set()

my set() = 8, 9, 6, 7, 5

but my code output for t2 is

my set() = 6, 7

(By the way for set() in python should it sort the value by default?)

Please help.

Is this what you are after?

def same_child_values(self, other):
 return set([c.item for c in self.children]) == set([c.item for c in other.children])

The key element is in the docstring: "We are only looking at values of the immediate children, not the descendants."