Find longest path in a search binary tree using C-CodePudding

I am having trouble finding the code for finding the longest path of a search binary tree using a recursive function.

void maxDepth(bst_node *node)
{            ....
}

The bst_node is a node of the search binary tree.

The condition of exitting the recursion is very simple:

if(node->leftChild==NULL&&node->rightChild==NULL)
{
return;
}

Before going to the recursion print the value of the node:

printf("%d ",node->value);

If lets say a node at depth x has only a left child then the longest path goes through the left child of the node and by using recursion we can write it like this:

if(node->rightChld==NULL)
{     
maxDepth(node->leftChild);
}

If a node at depth x has only a right child then the longest path goes through the right child of the node and by using recursion we can write it like this

if(node->leftChild==NULL)
{
maxDepth(node->rightChild);

}

But what if the node has both left and right child?I cannot understand how I can do this.Help appreciated.

CodePudding user response：

#define max(a, b) a > b ? a : b

int max_left = 0
int max_right = 0;    
if (node->rightChild != NULL) {
    max_right = maxDepth(node->rightChild);
}
if (node->leftChild != NULL) {
    mew_left = maxDepth(node->leftChild);
}
return max(max_left, max_right);

CodePudding user response：

The trick is to carefully think through each possible case. Either it's a base case, or you'll need to decompose it into a smaller problem you can solve with a recursive call.

int max(int a, int b) { return a > b ? a : b; }

int maxDepth(bst_node *node)
{
  // If the tree is empty, the depth is zero.
  if (!node) return 0;

  // If the right subtree is empty, it's this node plus the max height of the left.
  if (!node->rightChild) return 1   maxDepth(node->leftChild);

  // ...and symmetrically if the left subtree is empty.
  if (!node->leftChild) return 1   maxDepth(node->rightChild);

  // Otherwise there are two children. It's this node plus the max.
  return 1   max(maxDepth(node->leftChild), maxDepth(node->rightChild));
}