Skip to content

Instantly share code, notes, and snippets.

@ldong
Forked from t-mart/trip_advisor_tree.py
Created September 12, 2014 18:53
Show Gist options
  • Save ldong/787b68700c2c7ce5f033 to your computer and use it in GitHub Desktop.
Save ldong/787b68700c2c7ce5f033 to your computer and use it in GitHub Desktop.
class Node(object):
def __init__(self, name, lc=None, rc=None):
self.name = name
self.lc = lc
self.rc = rc
self.rn = None
# THE MEAT OF THE PROBLEM
@staticmethod
def link_rn(level_list):
lower_level_list = []
level_list_length = len(level_list)
if level_list_length == 0:
return
for i in range(level_list_length):
cur_node = level_list[i]
if i + 1 < level_list_length: # if there's a right neighbor
right_node = level_list[i + 1]
cur_node.rn = right_node
if cur_node.lc:
lower_level_list.append(cur_node.lc)
if cur_node.rc:
lower_level_list.append(cur_node.rc)
Node.link_rn(lower_level_list)
def print_right_neighbors(nodes):
for node in nodes:
if node.rn:
rn_name = node.rn.name
else:
rn_name = 'None'
print('%s -> %s' % (node.name, rn_name))
if __name__ == '__main__':
D, E, F, G = Node('D'), Node('E'), Node('F'), Node('G')
B, C = Node('B', D, E), Node('C', F, G)
A = Node('A', B, C)
all_nodes = [A, B, C, D, E, F, G]
print 'With no right linkage'
print '====================='
print_right_neighbors(all_nodes)
starter_level_list =[A]
Node.link_rn(starter_level_list)
print
print 'With right linkage'
print '====================='
print_right_neighbors(all_nodes)
# OUTPUT
# With no right linkage
# =====================
# A -> None
# B -> None
# C -> None
# D -> None
# E -> None
# F -> None
# G -> None
# With right linkage
# =====================
# A -> None
# B -> C
# C -> None
# D -> E
# E -> F
# F -> G
# G -> None
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment