二分木の深さを求める

Question

#include <stdio.h>
typedef struct node{
struct node *left;
struct node *right;
int data;
}NODE;

NODE *insert(NODE *tree,int x){
if(tree==NULL){
tree =(NODE *)malloc(size of(NODE));
tree->left =NULL; tree->right =NULL; tree->data=x;
}else if(x<tree->data) tree->left = insert(tree->left,x);
else tree->right = insert(tree->right,x);
return tree;
}

int maxDepth(NODE *tree){
if(tree==NULL) { return(-1); }
else {
if(.........)
return.........;
else return.........;
}
}

というプログラムで二分木の深さMaxDepthを求めたいのですが.......の部分が解りません。
どなたかよろしくお願いします。

皆様回答ありがとうございます。
確かに皆様のコードで実現可能なのですが、このプログラムは穴抜きの問題でして、......以外の部分には書けないのです。

Answer 1

参考情報：

• ２分探索木の高さを求めるプログラム http://okwave.jp/qa/q6915723.html

つまり、

• if(p==NULL){ return 0; } とする。
• max(右の子要素の深さ, 左の子要素の深さ) + 1 して、その要素の深さを求めるように再帰で計算する。

で計算できるとおもいます。

Answer 2

コメントで補足しましたが、以下のような形で実装できないでしょうか？

int maxDepth(NODE *tree){
if(tree==NULL) { return(-1); }
else {
/* 右の深さと左の深さを比較 */
if(.........)
/* 右の深さが大きい場合は、右の深さ+1 */
return.........;
/* 左の深さが大きい場合は、左の深さ+1 */
else return.........;
}
}

Answer 3

こういうふうに書いたら、分からないですかね。

int maxDepth(NODE *tree){
  if(tree==NULL) { return(-1); }
  else {
    int leftDepth = ....;
    int rightDepth = ....;
    if( .... )
      return .........;
    else
      return .........;
  }
}