Algorithm

Greatest Distance Between Two Nodes in Binary Tree

Nicholas Wong

Nicholas Wong

— 1 min read
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)

Read more