Implementation of a distance matrix of a binary tree that is given in the adjacency-list representation

Posted by Denise Giubilei on Stack Overflow See other posts from Stack Overflow or by Denise Giubilei
Published on 2012-09-02T15:37:21Z Indexed on 2012/09/02 15:37 UTC
Read the original article Hit count: 212

Filed under:

matrix

|

binary-tree

|

complexity

|

distance

|

adjacency-list

Given this problem I need an O(n²) implementation of this algorithm:

"Let v be an arbitrary leaf in a binary tree T, and w be the only vertex connected to v. If we remove v, we are left with a smaller tree T'. The distance between v and any vertex u in T' is 1 plus the distance between w and u."

This is a problem and solution of a Manber's exercise (Exercise 5.12 from U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).).

The thing is that I can't deal properly with the adjacency-list representation so that the implementation of this algorithm results in a real O(n²) complexity.

Any ideas of how the implementation should be?

Thanks.

© Stack Overflow or respective owner

Related posts about matrix

Find the "largest" dense sub matrix in a large sparse matrix

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a large sparse matrix (say 10k+ by 1M+) I need to find a subset, not necessarily continuous, of the rows and columns that form a dense matrix (all non-zero elements). I want this sub matrix to be as large as possible (not the largest sum, but the largest number of elements) within some aspect… >>> More
How does a template class inherit another template class?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a "SquareMatrix" template class which inherits "Matrix" template class, like below: SquareMatrix.h: #ifndef SQUAREMATRIX_H #define SQUAREMATRIX_H #include "Matrix.h" template <class T> class SquareMatrix : public Matrix<T> { public: T GetDeterminant(); }; template… >>> More
iPhone OpenGL ES: How do I use gravity vector to correctly transform scene for augmented reality

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying figure out how to get an OpenGL specified object to be displayed correctly according to the device orientation (ie. according to the gravity vector from the accelerometer, and heading from compass). The GLGravity sample project has an example which is almost like this (despite ignoring… >>> More
How do I use the gravity vector to correctly transform scene for augmented reality?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying figure out how to get an OpenGL specified object to be displayed correctly according to the device orientation (ie. according to the gravity vector from the accelerometer, and heading from compass). The GLGravity sample project has an example which is almost like this (despite ignoring… >>> More
C++ templates - matrix class

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi I'm learning templates in C++ so I decied to write matrix class which would be a template class. In Matrix.h file I wrote #pragma once #include "stdafx.h" #include <vector> using namespace std; template<class T> class Matrix { public: Matrix(); ~Matrix(); GetDataVector(); … >>> More

Related posts about binary-tree

finding two most distant elements in a binary tree

as seen on Stack Overflow - Search for 'Stack Overflow'
I am looking for an algorithm that could find the two most distant elements in a binary tree, not looking for any special language, just for the algorithm. Thanks. >>> More
Binary tree to get minimum element in O(1)

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm accessing the minimum element of a binary tree lots of times. What implementations allow me to access the minimum element in constant time, rather than O(log n)? >>> More
Binary Tree in C Insertion Error

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm quite new to C and I'm trying to implement a Binary Tree in C which will store a number and a string and then print them off e.g. 1 : Bread 2 : WashingUpLiquid etc. The code I have so far is: #include <stdio.h> #include <stdlib.h> #define LENGTH 300 struct node { int data; … >>> More
Simple Fundamental Algorithm Question, binary tree traversal

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to explain to non-computer science major student with many questions. (1)What traverses tree? Is it just logic or actual on off switch generates 1s and 0s traveling the circuit board? where is this tree and node exists CPU/Memory in between? (2)If it is 1s and 0s HOW the circuits understand… >>> More
How to create a Binary Tree from a General Tree?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have to solve the following constructor for a BinaryTree class in java: BinaryTree(GeneralTree<T> aTree) This method should create a BinaryTree (bt) from a General Tree (gt) as follows: Every Vertex from gt will be represented as a leaf in bt. If gt is a leaf, then bt will be a leaf… >>> More