# Traversing two trees until a common value has been found

I am traversing two objects that may share a common ancestor. To make the code small enough to show here, I have changed it into two dictionaries with values. As you can see, a_d and b_d are the inverse of each other. The idea is to step into each dictionary step by step until we find an overlapping value for the two. At each step the 'distance' is increased.

For the example case get_distance('b', 'y'), the output will print (comments added):

# init
start= b
end= y

# both a and b changed value (dist +1 for both) but no overlap found
start= c
end= x

# both a and b changed value (dist +1 for both) and an overlap was found!
start= d
end= d

Found overlap d
connected True


I hope that it is clear what this code does and what I am trying to do. Please keep in mind that the actual code works with elaborate objects and their properties, but the idea is similar. The issue that I am having is that the code is very repetitive and probably not as efficient as it could be. But I am not sure how I can improve on it. Ideas welcome!

def get_distance(start, end):
start_d = {
'a': 'b',
'b': 'c',
'c': 'd',
'd': 'x',
'x': 'y',
'y': 'z',
'z': 'z'
}

end_d = {
'z': 'y',
'y': 'x',
'x': 'd',
'd': 'c',
'c': 'b',
'b': 'a',
'a': 'a'
}

connected = False
start_dist = 0
end_dist = 0
while True:
print('start=', start)
print('end=', end)
print()

# Check whether a and b are the same, if so break
if start == end:
print(f"Found overlap {end}")
connected = True
break
# Check whether the next a value is the same as b, if so break and increase a_dist
elif start_d[start] == end:
print(f"Found overlap {end}")
start_dist += 1
connected = True
break
# Check whether the next b value is the same as a, if so break and increase b_dist
elif end_d[end] == start:
print(f"Found overlap {start}")
end_dist += 1
connected = True
break

# If for a and b all options are exhausted, break
if start == start_d[start] and end == end_d[end]:
break

# If a is not exhausted, get its dict value and increase distance
if start != start_d[start]:
start_dist += 1
start = start_d[start]

# If b is not exhausted, get its dict value and increase distance
if end != end_d[end]:
end_dist += 1
end = end_d[end]

dist = start_dist + end_dist
print('connected', connected)
return dist

if __name__ == '__main__':
dist = get_distance('b', 'y')


• text a= and b= can be missleading when you have also nodes a and b. Maybe start=, end= could be more readable. Jul 24 '19 at 0:59
• what if you have loops in data ? You will never exit from while. You should check how many steps you made - it can't be more then number of nodes. Jul 24 '19 at 1:01
• Maybe traversing in two directions can be sometimes faster - if one direction checked data faster then other direction - but traversing in one direction would need shorter code. Jul 24 '19 at 1:07
• Loops cannot occur (the actual, object-oriented data is on hierarchical data), so you don't have to think about that for now. Jul 24 '19 at 1:09
• I think better names would help understanding. Especially, what's the d in start_d and end_d ? And you talk about a tree, but if start/end correspond to actual parent/child, then you probably need something different, for when a node has several children. If it's for a tree again, I wouldn't bother traversing in 2 directions, you can just start from one node (unless you have very particular complexity requirements and statistics). Jul 24 '19 at 5:48

• Docstrings: You should include a docstring at the beginning of every method, class, and module you write. This will help documentation identify what your methods/classes/modules are supposed to accomplish.
• Simplicity: Rather than dist = start_dist + end_dist then returning dist, you can simply return start_dist + end_dist. You can return the addition of the two values, rather than creating a variable to only use it once to return. This is a personal preference, but it helps reduce the number of variables in the program, which helps me; and may also help you.
• Constants: Any constants in your program should be UPPERCASE. You only have one in your code, but you should keep in practice for when you write bigger programs.
• Printing: You use print(..., ...) and print(f"...") interchangeably. You should stick to using only one for consistency sake. As my preference, I changed all of them to print(f"..."), but you change choose your preference.

Updated Code

"""
Traverses two objects that may share a common ancestor
"""

def get_distance(start, end):
"""
Gets the distance from start to end in the trees
"""
start_d = {
'a': 'b',
'b': 'c',
'c': 'd',
'd': 'x',
'x': 'y',
'y': 'z',
'z': 'z'
}

end_d = {
'z': 'y',
'y': 'x',
'x': 'd',
'd': 'c',
'c': 'b',
'b': 'a',
'a': 'a'
}

connected = False
start_dist = 0
end_dist = 0

while True:
print(f"Start: {start}")
print(f"End: {end} \n")

# Check whether a and b are the same, if so break
if start == end:
print(f"Found overlap: {end}")
connected = True
break

# Check whether the next a value is the same as b, if so break and increase a_dist
elif start_d[start] == end:
print(f"Found overlap: {end}")
start_dist += 1
connected = True
break

# Check whether the next b value is the same as a, if so break and increase b_dist
elif end_d[end] == start:
print(f"Found overlap: {start}")
end_dist += 1
connected = True
break

# If for a and b all options are exhausted, break
if start == start_d[start] and end == end_d[end]:
break

# If a is not exhausted, get its dict value and increase distance
if start != start_d[start]:
start_dist += 1
start = start_d[start]

# If b is not exhausted, get its dict value and increase distance
if end != end_d[end]:
end_dist += 1
end = end_d[end]

print(f"Connected: {connected}")
return start_dist + end_dist

if __name__ == '__main__':
DISTANCE = get_distance('b', 'y')
print(f"Distance: {DISTANCE}")