Looking for fast algorithm to find distance between two nodes in binary tree

algorithm binary-tree
cboettig picture cboettig · Jan 25, 2010 · Viewed 25.5k times · Source

How do I find the distance between two nodes in a binary tree? Equivalently, what algorithms are there for finding the most recent common ancestor (lowest common ancestor) of two nodes?

Answer

Javier picture Javier · Jan 25, 2010
  1. calculate the list of ancestors for each node
  2. find the common prefix
  3. the last element from the common prefix is the lowest common ancestor
  4. remove the common prefix from both ancestor lists
  5. the distance is the sum of lengths of the remaining lists +1

Related questions

How to implement a binary tree?

Which is the best data structure that can be used to implement a binary tree in Python?

Read More
How to find the lowest common ancestor of two nodes in any binary tree?

The Binary Tree here is may not necessarily be a Binary Search Tree. The structure could be taken as - struct node { int data; struct node *left; struct node *right; }; The maximum solution I could work out with a friend …

Read More
The best way to calculate the height in a binary search tree? (balancing an AVL-tree)

I'm looking for the best way to calculate a nodes balance in an AVL-tree. I thought I had it working, but after some heavy inserting/updating I can see that it's not working correct (at all). This is kind of …

Read More