Minimum distance between two nodes in a binary tree

Given a binary tree, find the minimum distance between  two given nodes given that they exist ?

Comments

  1. - Find LCA or both nodes (say x,y). Call this LCA as node "L"
    - dist(x,y)=dist(root,x)+dist(root,y)-[2*dist(root,L)]

    Essentially, we are trying to compute:
    dist(x,y)=dist(x,L)+dist(y,L)

    Analysis: O(n) time complexity

    ReplyDelete
  2. @above yes you will have to compute LCA to find minimum distance between two nodes..

    ReplyDelete

Post a Comment

Popular posts from this blog

Circular game survival