Given a binary tree, find the deepest node in it.
Examples:
Input : Root of below tree
1
/
2 3
/ /
4 5 6 7
8
Output : 8
Input : Root of below tree
1
/
2 3
/
6
Output : 6
Method 1 : The idea is to do Inorder traversal of given binary tree. While doing Inorder traversal, we pass level of current node also. We keep track of maximum level seen so far and value of deepest node seen so far.
C++
// A C++ program to find value of the deepest node // in a given binary tree #include <bits/stdc++.h> using namespace std; // A tree node struct Node { int data; struct Node *left, *right; }; // Utility function to create a new node Node *newNode(int data) { Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // maxLevel : keeps track of maximum level seen so far. // res : Value of deepest node so far. // level : Level of root void find(Node *root, int level, int &maxLevel, int &res) { if (root != NULL) { find(root->left, ++level, maxLevel, res); // Update level and resue if (level > maxLevel) { res = root->data; maxLevel = level; } find(root->right, level, maxLevel, res); } } // Returns value of deepest node int deepestNode(Node *root) { // Initialze result and max level int res = -1; int maxLevel = -1; // Updates value "res" and "maxLevel" // Note that res and maxLen are passed // by reference. find(root, 0, maxLevel, res); return res; } // Driver program int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->right = newNode(7); root->right->right->right = newNode(8); root->right->left->right->left = newNode(9); cout << deepestNode(root); return 0; } |
Python3
"""Python3 program to find value of the deepest node in a given binary tree""" # A Binary Tree Node # Utility function to create a # new tree node class newNode: # Constructor to create a newNode def __init__(self, data): self.data= data self.left = None self.right = None self.visited = False # maxLevel : keeps track of maximum # level seen so far. # res : Value of deepest node so far. # level : Level of root def find(root, level, maxLevel, res): if (root != None): level += 1 find(root.left, level, maxLevel, res) # Update level and resue if (level > maxLevel[0]): res[0] = root.data maxLevel[0] = level find(root.right, level, maxLevel, res) # Returns value of deepest node def deepestNode(root) : # Initialze result and max level res = [-1] maxLevel = [-1] # Updates value "res" and "maxLevel" # Note that res and maxLen are passed # by reference. find(root, 0, maxLevel, res) return res[0] # Driver Code if __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.right.left = newNode(5) root.right.right = newNode(6) root.right.left.right = newNode(7) root.right.right.right = newNode(8) root.right.left.right.left = newNode(9) print(deepestNode(root)) # This code is contributed by # SHUBHAMSINGH10 |
Output:
9
Time Complexity: O(n)
Method 2 : The idea here is to find the height of the given tree and then print the node at the bottom-most level.
C++
// A C++ program to find value of the // deepest node in a given binary tree #include <bits/stdc++.h> using namespace std; // A tree node with constructor class Node { public: int data; Node *left, *right; // constructor Node(int key) { data = key; left = NULL; right = NULL; } }; // Utility function to find height // of a tree, rooted at 'root'. int height(Node* root) { if(!root) return 0; int leftHt = height(root->left); int rightHt = height(root->right); return max(leftHt, rightHt) + 1; } // levels : current Level // Utility function to print all // nodes at a given level. void deepestNode(Node* root, int levels) { if(!root) return; if(levels == 1) cout << root->data; else if(levels > 1) { deepestNode(root->left, levels - 1); deepestNode(root->right, levels - 1); } } // Driver program int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->left = new Node(5); root->right->right = new Node(6); root->right->left->right = new Node(7); root->right->right->right = new Node(8); root->right->left->right->left = new Node(9); // Calculating height of tree int levels = height(root); // Printing the deepest node deepestNode(root, levels); return 0; } |
Python3
# A Python3 program to find value of the # deepest node in a given binary tree class new_Node: def __init__(self, key): self.data = key self.left = self.right = None # Utility function to find height # of a tree, rooted at 'root'. def height(root): if(not root): return 0 leftHt = height(root.left) rightHt = height(root.right) return max(leftHt, rightHt) + 1 # levels : current Level # Utility function to prall # nodes at a given level. def deepestNode(root, levels): if(not root): return if(levels == 1): print(root.data) elif(levels > 1): deepestNode(root.left, levels - 1) deepestNode(root.right, levels - 1) # Driver Code if __name__ == '__main__': root = new_Node(1) root.left = new_Node(2) root.right = new_Node(3) root.left.left = new_Node(4) root.right.left = new_Node(5) root.right.right = new_Node(6) root.right.left.right = new_Node(7) root.right.right.right = new_Node(8) root.right.left.right.left = new_Node(9) # Calculating height of tree levels = height(root) # Printing the deepest node deepestNode(root, levels) # This code is contributed by PranchalK |
Output:
9
Time Complexity: O(n)
Thanks to Parth Patekar for suggesting above method.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments