You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

# 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

# answer should be 5
print get_max_length(root)
``````
Algorithm

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.