Height of tree is used to find the maximum number of steps to search for an item in a data set using logarithmic division.
If you wanted to find a number in that tree, you compare the toFind integer with the current node. If larger, go down right side. If smaller, go down left side.
You may find your integer at the very top, or at the next node, or a few steps down the tree. But the absolute maximum number of steps it takes to find your item is the height of the tree.
By going down 1 step, you’ve removed half of the data set by process of elimination. For example, if you search for a 2, and the node is 8, you go down the left side. You don’t need to worry about the right side of 8, because all those numbers is guaranteed to be bigger.
With each step you take, you eliminate half of the data set until you finally get to your number.
The number of eliminations (or divisions) you make is basically the height of the tree.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int MyBST::height(Node * node) { if(node== NULL) { return 0; } else { cout << "...on node : " << node->data << endl; int leftHeight = height(node->left); int rightHeight = height(node->right); if((node->right) == NULL && (node->left == NULL)) return 0; //if its a leaf, its a 0 else { if(leftHeight > rightHeight) return (leftHeight + 1); else return (rightHeight + 1); } } } |
1) get the height of the tree
2) Go through each level of the height and print
|
1 2 3 4 5 6 7 8 9 10 |
void MyBST::printBFS(struct Node * root) { int h = height(root); for (int i=0; i<=h; i++) { cout << "\n------printing for level: " << i << "-------------" << endl; printGivenLevel(root, i); //i is how many steps to go down } } |
level is how many depths to go into the tree..
0 is root
1 means go down 1 level..display all nodes there.
2 means go down 2 levels…display all nodes there..
etc
NOTICE LEVEL. we recursively traverse via LEVEL
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void MyBST::printGivenLevel(struct Node * root, int level) { if (root == NULL) return; if (level == 0) { printf("\nNode, reached, printing: %lld ", root->data); } else if (level > 0) { cout << "\nmoving down a level" << endl; printGivenLevel(root->left, level-1); // as you traverse, you decrement depth so know when to stop printGivenLevel(root->right, level-1); } } |