Home Trees Write a program to find the deepest node in a binary tree?

# Write a program to find the deepest node in a binary tree?

0 comment

Question: Given the root pointer to a binary tree, find the deepest node.

According to the definition, the deepest node in a binary tree is the last element in the binary tree while performing a level order traversal. In the above case, therefore we have “5” as the deepest node in the tree.

We can simply follow a level order traversal approach to solve this problem. Just return the last element to get the deepest node.

Here is the implementation:-

#include<stdio.h>
#include<malloc.h>

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

struct binaryTreeNode * deepestNode(struct binaryTreeNode * root)
{
// Level order traversal
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;

if(root == NULL)
return;
Q = enQueue(Q, root);
while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;
Q = deQueue(Q);
if(temp -> left)
Q = enQueue(Q, temp -> left);
if(temp -> right)
Q = enQueue(Q, temp -> right);
}
// Delete the queue
free(Q);

// Now return the last node
return temp;
}


Time Complexity:- O(n)
Space Complexity:- O(n)

Ideone link for the running code:- http://ideone.com/tln1QD

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More