Binary Search tree inside Binary Search tree?

I have given an example implementation of this below, commented to explain how I approached this. You should be able to use my ideas to modify the way your code works. Note that its not a perfect implementation, off the top of my head, I can see the following problems.

I have given an example implementation of this below, commented to explain how I approached this. You should be able to use my ideas to modify the way your code works. Note that its not a perfect implementation, off the top of my head, I can see the following problems.

Its recursive, which means the depth of tree it can handle is limited by the size of the stack on the target machine. There are two ways you can attack this, either: Make it iterative. That is, use for/while loops instead of functions calling themselves - this would allow for as many nodes as your machines memory can handle (fixes the problem).

Update add_name_to_tree to handle insertions for a balanced binary tree (but this just helps the issue, the stack limit is still there). It can't handle two people with exactly the same name, but different id's - after the first person is added to the tree, all subsequent people of the same name are ignored. I will leave it as an exercise for you to handle these situations.

#include #include /* a single struct type for storing all tree elements */ typedef struct _node { char name50; int id; struct _node *subname; struct _node *left; struct _node *right; } node; /* creates a new node structure for the specified name and id */ node *create_node(const char *name, int id) { node *newNode = (node*)malloc(sizeof(node)); memset(newNode, 0, sizeof(*newNode)); newNode->id = id; strncpy(newNode->name, name, sizeof(newNode->name)); return newNode; } /* inserts the name/id pair into the tree specified by root. Note that root is passed as a pointer to a pointer, so that it can accept NULL if no tree exists yet, and return to the caller the node the node that contains the name. Note that id is ignored if "name" already exists, i'll leave it as an excersice for you to handle situations with the same name with multiple id's */ node *add_name_to_tree(node **root, const char *name, int id) { if (*root == NULL) { *root = create_node(name, id); return *root; } const int cmp = strcmp(name, (*root)->name); if (cmp left, name, id); } else if (cmp > 0) { return add_name_to_tree(&(*root)->right, name, id); } else { return *root; } } /* adds the specified first/last name and id combo to the tree specified by root */ node *add_name(node *root, const char *first, const char *last, int id) { /* this call will return the node that holds the last name, we can then use its "subname" tree root to insert the first name */ node *last_node = add_name_to_tree(&root, last, 0); /* use the "subname" of the node that stores the last name as the root of the tree that stores first names */ add_name_to_tree(&last_node->subname, first, id); return root; } /* just to demonstrate why I use the same node type for first/last names, its because it allows you to support any number of names, see below - an add function that adds people with a middle name to the tree */ node *add_with_middle_name(node *root, const char *first, const char *middle, const char *last, int id) { node *last_node = add_name_to_tree(&root, last, 0); node *mid_node = add_name_to_tree(&last_node->subname, middle, 0); add_name_to_tree(&mid_node->subname, first, id); return root; } /* recursively traverse the name tree, printing out the names */ void print_names(node *names, int level) { const int indent = 10; if (names == NULL) { printf("\n"); } if (names->left) { print_names(names->left, level); } if (names->subname) { printf("%*c %s \n", (indent * level), ' ', names->name); print_names(names->subname, level + 1); printf("\n"); } else { printf("%*c %-*s %d\n", (indent * level), ' ', indent, names->name, names->id); } if (names->right) { print_names(names->right, level); } } int main() { node *names = NULL; names = add_name(names, "Sylvester", "Stallone", 11111111); names = add_name(names, "Noah", "Stallone", 22222222); names = add_name(names, "Chuck", "Norris", 33333333); names = add_name(names, "Hulk", "Hogan", 44444444); names = add_name(names, "Daniel", "Hogan", 55555555); names = add_with_middle_name(names, "Peter", "Michael", "Zachson", 66666666); print_names(names, 0); return 0; }.

Thank you very very very much! You saved my live! – Spyros May 30 at 14:49.

925, 202, 911, 240, 912, 245, 363 Doesn't make sense From 911, you're taking the smaller branch to 240. You then somehow arrive at 912. This should be impossible If the left child of any node is smaller than its parent, then ALL elements in the left subtree should be smaller than their parent.912 > 911, therefore it's in the wrong subtree.

Doesn't make sense From 911, you're taking the smaller branch to 240. You then somehow arrive at 912. This should be impossible.

If the left child of any node is smaller than its parent, then ALL elements in the left subtree should be smaller than their parent. 912 > 911, therefore it's in the wrong subtree.

Aha,I get it the left sub tree should be less than the right sub tree thanks for your answer – user355002 Jun 26 '10 at 16:21 @matin1234 What I was trying to say is that the entire left sub tree should be less than the parent, not just less than the right sub tree – Jamie Wong Jun 26 '10 at 16:25 aha now I get the whole thanks – user355002 Jun 26 '10 at 16:45.

Nt: When searching in a sorted BST, the upper and lower bounds should only get tighter.

Try drawing various trees on a paper and see what you get. Remember that a binary tree is defined as a tree where each node may have 0 (in which case it is a leaf), 1 or 2 children. For your question you should examine the very unbalanced case of 1 child per node.

Consider: If you're trying to maximize the number of leaves, you want as few internal nodes as possible (and the reverse if you're trying to minimize the number of leaves). How can you accomplish that? To get a tree of maximal height, you'll put as few nodes in each level as possible.

How can you do that? Conversely, for the minimum height, what is the maximum number of nodes you can put at each level? How many ways are there to get to each node of a tree?

Thus, how many pointers do you need?

The maximum number of leaves is ceil(n / 2). The minimum number is 1 The maximum height is n. The minimum is floor(log_2(n)).

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: int height(struct node *tree) { if (tree == NULL) return 0; return 1 + max (height (tree->left), height (tree->right)); } Read more: wiki.answers.com/Q/How_do_you_find_out_t... 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 forums.techarena.in/software-development... can help you: check if root is null, then pass the left and right nodes as parameters into the function.Int countnodes(Node* root) { if (root == null || kInt totalnodes = countnodes(root) - 1; 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. ;).

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.