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

Nicholas Wong
Nicholas Wong

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.