2.9K
Question: Given the root pointer to a binary tree, find the deepest node.
Input: Sample Tree (Pointer to node 1 is given).
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
