StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
6114535
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2011-05-24T17:39:56.457
FavoriteCount
0
LastActivityDate
2011-05-24T17:45:31.293
LastEditDate
2011-05-24T17:45:31.293
LastEditorUserId
759929
OwnerUserId
759929
ParentId
6114402
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
I'm assuming you're either coding in C or C++. a. A node, if the structure is defined like this: struct node { struct node *left, *right; }; You can observe that the structure can either have 0, 1, or 2 leaves. So, the max is 2, min is 0 leaves. b.Minimal height is zero, in which would only contain the root node. Note that the root node does not count as a height of 1. It's also called depth at times. Here is an algorithm for the height: <pre><code> int height(struct node *tree) { if (tree == NULL) return 0; return 1 + max (height (tree->left), height (tree->right)); } </code></pre> Read more: <a href="http://wiki.answers.com/Q/How_do_you_find_out_the_height_of_a_Binary_Search_Tree#ixzz1NIB17SkL" rel="nofollow">http://wiki.answers.com/Q/How_do_you_find_out_the_height_of_a_Binary_Search_Tree#ixzz1NIB17SkL</a> c. Pardon me if I take this the worng way, but I'm assuming if we mapped this out on a piece of paper, we'd be trying to find the number of "links" that we would use? In that case, it'd simply be the number of nodes in the tree -1 for root node. This algorithm found on this page <a href="http://forums.techarena.in/software-development/1147688.htm" rel="nofollow">http://forums.techarena.in/software-development/1147688.htm</a> can help you: check if root is null, then pass the left and right nodes as parameters into the function. <pre><code>int countnodes(Node* root) { if (root == null || k<=0) { return 0; } else { return 1 + count(root.left,k-1) + count(root.right,k-1); } } // remember to subtract one at the end. int totalnodes = countnodes(root) - 1; </code></pre> d. The time complexity for best case is O(nlogn) where n is the number of nodes to insert. The worst case, is O(n). It is directly linear. If you have any other questions just google it, there's plenty of things to know about binary search trees. But most of it is simply recursion that you can learn in 30 seconds. I hope this helps. Good luck on your exam! I had mine a few months ago. ;)
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POBinary Search Tree
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. UStf.rz
UserOwnerUserId
1. UStf.rz
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.