[go: up one dir, main page]
Scribd
Upload
20 views2 pages

Binary Tree

This document contains a C program that implements a binary tree with functionalities to calculate the maximum depth of the tree and find the level of a given node. It defines a structure for tree nodes, functions to create new nodes, compute maximum depth, and retrieve the level of a specific value in the tree. The main function demonstrates these functionalities by creating a sample tree and printing the depth and levels of nodes from 1 to 5.

Uploaded by

lekhanar14
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
20 views2 pages

Binary Tree

This document contains a C program that implements a binary tree with functionalities to calculate the maximum depth of the tree and find the level of a given node. It defines a structure for tree nodes, functions to create new nodes, compute maximum depth, and retrieve the level of a specific value in the tree. The main function demonstrates these functionalities by creating a sample tree and printing the depth and levels of nodes from 1 to 5.

Uploaded by

lekhanar14
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

#include <stdio.

h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child and a pointer to right child
*/

struct node
{
int data;
struct node* left;
struct node* right;
};

/* Compute the "maxDepth" of a tree -- the number of nodes along the longest path
from the root node down to the farthest leaf node.*/

int maxDepth(struct node* node)


{
if (node == NULL)
return 0;
else {
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);

/* use the larger one */


if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}

/* Helper function that allocates a new node with the given data and NULL left and
right pointers. */

struct node* newNode(int data)


{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

// Helper function for getLevel(). It returns level of the data if data is present
in tree, otherwise returns 0.

int getLevelUtil(struct node* node, int data, int level)


{
if (node == NULL)
return 0;

if (node->data == data)
return level;

int downlevel = getLevelUtil(node->left, data, level + 1);


if (downlevel != 0)
return downlevel;

downlevel = getLevelUtil(node->right, data, level + 1);


return downlevel;
}

/* Returns level of given data value */

int getLevel(struct node* node, int data)


{
return getLevelUtil(node, data, 1);
}

int main()
{
struct node* root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);

printf("Depth of Height of tree is %d \n", maxDepth(root));

for (int x = 1; x <= 5; x++)


{
int level = getLevel(root, x);
if (level)
printf(" Level of %d is %d\n", x,
getLevel(root, x));
else
printf(" %d is not present in tree \n", x);
}

getchar();
return 0;
}

You might also like