CODEWITHSUNDEEP
crecursionbinary-search-tree
Miss Mulan
Miss Mulan

Reputation: 123

Find longest path in a search binary tree using C

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.

For example with this binary search tree the output should be:

"11 13 57 25 17"

Help appreciated.

Upvotes: 0

Views: 545

Answers (2)

Gene
Gene

Reputation: 46960

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;

  // Otherwise it's this node plus the max of the children.
  return 1 + max(maxDepth(node->leftChild), maxDepth(node->rightChild));
}

Upvotes: 1

imperosol
imperosol

Reputation: 578

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

int maxDepth(bst_node *node) {
    if (node == NULL) {
        return 0;
    }
    int max_left = maxDepth(node->leftChild);
    int max_right = maxDepth(node->rightChild);
    return max(max_left, max_right) + 1;
}

Upvotes: 0

Related Questions