Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

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

Tags:

algorithm

binary-tree

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?

like image 223
cboettig Avatar asked Jan 25 '10 18:01

cboettig

People also ask

How do you find the distance between two nodes in a binary tree?

The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula. Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree.

What is the distance between two nodes?

The distance between two nodes is defined as the total number of edges in the shortest path from one node to other. For example, consider the binary tree. The distance between node 7 and node 6 is 3. This problem is a standard application of the lowest common ancestor of given nodes.

1 Answers

  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
like image 153
Javier Avatar answered Oct 16 '22 01:10

Javier
Sign in to Comment

Related questions

How to store infinity in a BigDecimal (Java)?
Find missing number in bit array
How can I write an interpreter for 'eq' for Hack Assembly language?
Best time to buy and sell stocks when allowing consecutive buys or sells
Regarding in-place merge in an array
Given two (large) sets of points, how can I efficiently find pairs that are nearest to each other?
Pairwise sum of n numbers in non increasing order
std::lower_bound slower for std::vector than std::map::find
Circle covering algorithm with varying radii
Permutation job scheduling with partial available machines
Drawing Directed Acyclic Graphs: Minimizing edge crossing?
Better algorithm to find average [closed]
worst case in MAX-HEAPIFY: "the worst case occurs when the bottom level of the tree is exactly half full"
WordCount: how inefficient is McIlroy's solution?
Algorithm for checking if a string was built from a list of substrings
Generalizing the find-min/find-max stack to arbitrary order statistics?
Does this prime function actually work?
how to match dna sequence pattern
optimized way to search a device ip address within a range in iphone
How to create an optimized 3D volume-packing function in python?

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!