Height of Binary Search Tree (Iterative) in C

general
, , ,
1

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

2

go to the link

http://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/ (recursive)
this article have complete explaination of your question :slight_smile: enjoy :smiley:

hope this will help you :slight_smile:

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;

}

1 Like
3

its recursive.

4

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

5

updated :slight_smile:

6

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