Distance between two BST nodes

How do you find the distance between two nodes in a binary search tree? For example, in this one:

http://img232.imageshack.us/img232/649/81160f4ad65a7edc5353e76py8.jpg

the distance between 5 and 15 is 3, and the distance between 5 and 17 is 5. Every cell I've implemented is an object with a "datum" (the integer value), node.right, and node.left (every node's children).

I was thinking on adding the 'depths' of the nodes to search relative to the lower-most parent where they split up, which I guess kinda works in theory but I've found its recursive implementation to be a pain. I'm probably over-complicating this, but I'm running out of ideas.

I guess another option is to keep track of the parent in addition of the datum, left, and right? Ideas?

[790 byte] By [coprolitoa] at [2007-11-27 11:05:56]

«« Creating a url-pattern with a wildcard at the start
»» Help Please - exam question

# 1

Finding the depth of a tree is a relatively simple algorithm, google for "binary tree depth algorithm". You can specialize that algorithm to find the depth between two specific nodes.

First, find the higher node, using binary search.

From that node, use binary search to find the lower node.

Use the depth algorithm to recursively find the depth between the two.

That's pretty basic, so there are probably ways to simplify it.

hunter9000a at 2007-7-29 13:11:59 >

Java Essentials

New To Java

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

Distance between two BST nodes

Java Essentials New Topic

Java Essentials Hot Topic

Java Essentials

All Classified