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?
That is what is necessary to make it works because there is no need to go deeper level to connect your children’s sibling.
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?
I would suggest you to use our judge framework to test your algorithm and then you shall understand that more!
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.
Would you mind to share your working code here as I am curious about this?
Sure. We can refer the official Solutions (http://elementsofprogramminginterviews.com/solutions/) for “Compute the right sibling tree” problem:
while start_node and start_node.left:
# Populate left child's next field.
start_node.left.next = start_node.right
# Populate right child's next field if iter is not the last node of
start_node.right.next = start_node.next and start_node.next.left
start_node = start_node.next
while tree and tree.left:
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.
Turns out it is just inconsistency of solutions between Python and other languages, we do exclude this check in C++ and Java.