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?

by nikoo28
0 comment

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

Input: Sample Tree (Pointer to node 1 is given).
tree_insert_element_1
Output: 5

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

Enclose codes in [code lang="JAVA"] [/code] tags

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