Get the greatest distance between two nodes in a binary tree. Assume links between nodes are bidirectional. Distance is defined as the amount of nodes connected along the path linked two nodes. Write an algorithm to calculate distance between two nodes. Take the figure at the right, the greatest length should be 4.
Usual post-order recursive binary tree traversal should do the job. In this case, (obviously) the path must passes through the root. So we should do the following. Recursively return the max length (from left or right) to the parent, and make an exception for the root. The result is simply the sum of maxes from left and right.
# node structure class Node: def __init__(self, left=None, right=None): self.left = left self.right = right # join left and right max at root, literally def get_max_length(root): left_max = length_from_node(root.left) right_max = length_from_node(root.right) return left_max + right_max # returning the max length beginning from this node def length_from_node(node): if not node: return 0 left_max = length_from_node(node.left) right_max = length_from_node(node.right) return max(left_max, right_max) + 1 # binary tree setup node_12 = Node() node_13 = Node() node_05 = Node() node_07 = Node(node_12, node_13) node_09 = Node() node_11 = Node() node_06 = Node(node_05, node_07) node_10 = Node(node_09, node_11) node_08 = Node(node_06, node_10) root = node_08 # answer should be 5 print get_max_length(root)
Nicholas Workshop Newsletter
Join the newsletter to receive the latest updates in your inbox.