This is the scenario:
1. user inputs an int N for the desired level
2. if N is greater than the total number of levels in the tree, repeat input
3. if N is less than 0, repeat input
4. if N is okay, print all the nodes belonging to this level.
1-3 I know how to do, but 4 is a mystery
I thought about putting all the nodes into an array, and then manually checking each of them if they are of the required level, but I'm not sure if that would take for ever
It depends how your binary tree is represented. Is this a struct containing two spanning nodes (left and right)? Or an array?
Let's say your binary tree is an array:
Index of left node of i-th node, is: i * 2 + 1Code:nodes (i): 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | levels: 0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Index of right node of i-th node, is: i * 2 + 2
First node of n'th level is:
2^n-1
(number of nodes for each level is 2^n).
Last edited by kmdv; 09-05-2010 at 09:23 AM.
It'd be like any other traversal function only you have to keep track of what level you're at. When you reach that level, print and stop going deeper.
Totally untested mostly real C code :
Code:void print_at_level(Node *node, int desired, int current) { if (node) { if (desired == current) print(node); else { print_at_level(node->right, desired, current + 1); print_at_level(node->left, desired, current + 1); } } }
top level call would be something like :
Code:print_at_level(root, 0, 5)
Last edited by KCfromNC; 09-08-2010 at 06:19 AM. Reason: Told you it was untested
One decremented parameter is enough.Originally Posted by KCfromNC
