Author |
Topic: Height of BST (Read 1443 times) |
|
harsh487
Newbie
Posts: 6
|
 |
Height of BST
« on: Nov 17th, 2008, 10:27am » |
 Quote  Modify
|
The problem is to find the height of a BST....
and we are given a doubly linklist in which the leaf nodes of binary search tree are stored....
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Height of BST
« Reply #2 on: Nov 18th, 2008, 1:04am » |
Quote Modify
|
If it is perfectly balanced, the length of the list should be enough to find the height.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Height of BST
« Reply #3 on: Nov 18th, 2008, 2:05am » |
Quote Modify
|
True, but you'd still go through about half the elements; which isn't much better than going through all, as the regular algorithm for finding the depth does. And the latter also works if the tree isn't balanced.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
harsh487
Newbie
Posts: 6
|
|
Re: Height of BST
« Reply #4 on: Nov 19th, 2008, 10:43am » |
Quote Modify
|
its one of the cases that when it will be perfectly balanced then it will work.....But we have not been given tree ...So we dont know whether tree is completely balanced or not....So how to tell then....
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Height of BST
« Reply #5 on: Nov 19th, 2008, 2:36pm » |
Quote Modify
|
If all you have is a doubly linked list of all the leaf nodes, what do you know about the structure of the tree?
You could have
1
/ \
2 3
/ \ / \
A B C D
or
1
/ \
A 2
/ \
B 3
/ \
C D
In both case you have the list
A - B - C - D
but the depth is different. Or maybe I didn't understand the question.
|
|
IP Logged |
|
|
|
scm007
Newbie
Posts: 11
|
|
Re: Height of BST
« Reply #6 on: Dec 26th, 2008, 10:52am » |
Quote Modify
|
I'm guessing you have both a pointer to the root node and this doubly linked list.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print