On Jun 30, 2009, at 1:05 AM, Emeka wrote:
> Hello All,
>
> I have a BinaryTree Nodes that I want to resolve it's depth and the
> BinaryTree may be unbalanced. How do I do this? Can't just figure it
> out on my own?
> It is in the form of vector of vectors, and from one cell of any
> vector I can move to the next row however the column index has to
> be either increased by one or decreased by one(and the new cell is
> empty).
If you had a balanced binary tree, you could just take log_2(N) where
N is the number of nodes. :) But since you don't you have to do
something like get the max depth of the left branch and the right
branch and add one to it (pseudocode):
(defn depth [tree]
(if (nil? tree) 0
(+ 1 (max (depth (left tree)) (depth (right tree)))))
If you're storing this binary tree in an array, I vaguely remember
doing something like storing the left node at 2*i where i is the index
of the current node, and the right node at 2*i+1. I'm not sure how
you'd do that with an unbalanced tree unless you did something like
have nils in your array. If you did that, you just need to take
log_2(I) where I is the index of the last non-nil value in the array.
I'm not sure exactly what data structure you're working with to make
your binary tree though. Can you send an example of the tree you have
as vectors?
Are you also trying to compute whether or not it's unbalanced or is
that just a given that it might be?
—
Daniel Lyons
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
