Tutorialspoint.dev

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



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.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter