# Greatest Distance Between Two Nodes in Binary Tree

## Question

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.

## Solution

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.

## Example

``````# 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