# Height of Binary Search Tree (Iterative) in C

I want to know the algorithm to find the height of any BST in C.

http://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/ (recursive)

int maxDepthIterative(BinaryTree *root) {

if (!root) return 0;

stack<BinaryTree*> s;

s.push(root);

int maxDepth = 0;

BinaryTree *prev = NULL;

while (!s.empty()) {

``````BinaryTree *curr = s.top();

if (!prev || prev->left == curr || prev->right == curr) {

if (curr->left)

s.push(curr->left);

else if (curr->right)

s.push(curr->right);

} else if (curr->left == prev) {

if (curr->right)

s.push(curr->right);

} else {

s.pop();

}

prev = curr;

if (s.size() > maxDepth)

maxDepth = s.size();
``````

}

return maxDepth;

}

2 Likes

its recursive.

this link could help…it is an SO link…has both rec as well as iterative version…

updated

Idea: Every time nodeCount is set, the scan is just about to start a new row. nodeCount is set to the number of nodes in that row. When all of those nodes have been removed (i.e., nodeCount is decremented to zero), then the row has been completed and all the children of nodes on that row have been added to the queue, so the queue once again has a complete row, and nodeCount is again set to the number of nodes in that row. Source

Pseudo-Code:

``````Create a Queue, and push the root into it
Let Depth = 0
Loop:
Let nodeCount = size(Queue)
If nodeCount is 0:
return Depth
Increment Depth
While nodeCount > 0:
Remove the node at the front of the queue
Push its children, if any, on the back of the queue
Decrement nodeCount
``````
//