Friday, 16 January 2015

Finding the maximum and minimum depth of the binary trees in C++ with examples

Finding the maximum and minimum depth of the binary trees in Cpp with examples:

As we have seen before post we have bit knowledge about creating, inserting and getting size of the binary trees.

GetMaximumDepth()
Given a binary tree, compute its "GetMaximumDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node.

Syntax of the function is

int GetMaximumDepth(struct node* node)


Here we are passing root node as an argument. It returns the maximum depth.

GetMinimumDepth()

Given a non-empty binary search tree, return the minimum data value found in that tree.
Note that it is not necessary to search the entire tree.

Note:This can be solved with recursion or with a simple while loop.


int GetMinimumDepth (struct node* node) 


Here we are passing root node as an argument. It returns the minimum depth.


Example Code for the GetMaximumDepth() in C++:

This helps us to get the number of nodes along the longest path from the root node down to the farthest leaf node.

int GetMaximumDepth (struct stNode* pstNode)
{
if (pstNode == NULL)
  { return (0); }
else {
int lDepth = GetMaximumDepth (pstNode->left);
int rDepth = GetMaximumDepth (pstNode->right);
if (lDepth > rDepth)
  return(lDepth + 1);
else
  return (rDepth + 1);
}
}


Example Code for the GetMinimumDepth() Solution (C/C++)

Given a non-empty binary search tree, return the minimum data value found in that tree. Note that the entire tree does not need to be searched.

int GetMinimumDepth (struct stNode* pstNode)
{
  struct stNode* pstCurrent = pstNode;
  while (->left != NULL)
    { pstCurrent = pstCurrent->left; }
  return (pstCurrent->data);
}

No comments: