EPI Python 9.16 Code - Redundant condition?

#1

construct_right_sibling_tree() and populate_children_next_field() both check this specific terminating condition (tree.left, start_node.left).

Is this deliberately redundant or is there a reason for this check to exist in both the methods?

0 Likes

#2

That is what is necessary to make it works because there is no need to go deeper level to connect your children’s sibling.

0 Likes

#3

Isn’t the check for tree.left in construct_right_sibling_tree() sufficient to prevent the code from going deeper (to the leaves and below)?

Am I overseeing a case where checking start_node.left in the called method populate_children_next_field() is crucial for the algorithm to work?

0 Likes

#4

I would suggest you to use our judge framework to test your algorithm and then you shall understand that more!

0 Likes

#5

Thanks, I just ran my code using the EPI Judge framework. It was logical to me that we don’t need to repeat the check in two places, but the framework helped confirm this.

0 Likes

#6

Hi @interviewing.joe,

Would you mind to share your working code here as I am curious about this?

0 Likes

#7

Sure. We can refer the official Solutions (http://elementsofprogramminginterviews.com/solutions/) for “Compute the right sibling tree” problem:

  1. def construct_right_sibling(tree):
    
  2.     def populate_children_next_field(start_node):
    
  3.         while start_node and start_node.left:
    
  4.             # Populate left child's next field.
    
  5.             start_node.left.next = start_node.right
    
  6.             # Populate right child's next field if iter is not the last node of
    
  7.             # level.
    
  8.             start_node.right.next = start_node.next and start_node.next.left
    
  9.             start_node = start_node.next
    
  10.     while tree and tree.left:
    
  11.         populate_children_next_field(tree)
    
  12.         tree = tree.left
    

The check for tree.left on line 10 and start_node.left on line 4 are redundant - only one check on the left node is sufficient for the program to provide the correct result.

0 Likes

#8

Turns out it is just inconsistency of solutions between Python and other languages, we do exclude this check in C++ and Java.

0 Likes