CODEWITHSUNDEEP
c++algorithmbinary-tree
Aaron
Aaron

Reputation: 4480

How would you find the min depth of a tree?

I know how to find the max depth of a tree using a stack and inorder traversal, but I cannot figure out how to find the min depth of a tree (not necessarily a BST) using a stack or queue instead of recursive calls.

Upvotes: 1

Views: 1433

Answers (2)

KMC
KMC

Reputation: 1742

I know this was asked long time ago but for those who stumbled upon here and would rather not use recursion, here's my pseudo (My apology for not providing C++ code because I'm not verse in C++). This leverage BFS traversal.

return 0 if root is empty

queue a tuple (that stores depth as 1 and a root node) onto a queue

while queue is not empty
   depth, node = dequeue queue
   // Just return the depth of first leaf it encounters
   if node is a leaf then : return depth
   if node has right child: queue (depth+1, node.right)
   if node has left child : queue (depth+1, node.left)

Time complexity of this one is linear.

Upvotes: 0

Srikar Appalaraju
Srikar Appalaraju

Reputation: 73588

One thing to note here is that when you perform recursion you are using your process execution stack. This generally has some limit set by OS. So with each recursion the process state is pushed onto this stack. So at some point stackoverflow occurs.

If you end up doing a iterative version as apposed to recursive, note that the difference here is that this stack implementation is maintained by you. There is lot more work involved but stackoverflow is averted...

We could do something like the following (recursive version)-

MIN-VALUE

int min = INT_MAX;
void getMin(struct node* node)
{
     if (node == NULL)
          return;

     if(node->data < min)
          min = node->data;

     getMin(node->left);
     getMin(node->right);

     return min;
}

Alternatively you could use min-heap which gives you minimum value in constant time.

UPDATE: Since you changed your question to min-depth

MIN-DEPTH

#define min(a, b) (a) < (b) ? (a) : (b)

typedef struct Node
{
    int data;
    struct Node *left, *right;

}Node;

typedef Node * Tree;

int mindepth(Tree t)
{
    if(t == NULL || t->left == NULL || t->right == NULL)
        return 0;

    return min( 1 + mindepth(t->left), 1 +  mindepth(t->right) );
}

PS: Code is typed freehand, there might be syntactical errors but I believe logic is fine...

Upvotes: 3

Related Questions