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 site uses Akismet to reduce spam. Learn how your comment data is processed.

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