# Find the Deepest Node in a Binary Tree

Given a binary tree, find the deep­est 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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 ` `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.

Tree Tree