Tutorialspoint.dev

Depth of the deepest odd level node in Binary Tree

Given a Binary tree, find out depth of the deepest odd level leaf node. Take root level as depth 1.

Examples:

Input : 
diagram1
Output : 5

Input : 10
       /     
     28       13
            /     
          14       15
                  /  
                 23   24
Output : 3



We can traverse the tree starting from the root level and keep curr_level of the node.
Increment the curr_level each time we go to left or a right subtree.
Return the max depth of an odd level,if it exists.

Algorithm:

    1) return 0 if curr_node == NULL
    2) if curr_node is leaf and curr_level is odd, 
       return curr_level
    3) else maximum(depthOdd(left subtree), 
                    depthOdd(right subtree))

Below is the implementation.

C++

// C++ program to find depth of the deepest
// odd level node
#include<bits/stdc++.h>
using namespace std;
  
// A Tree node
struct Node
{
    int key;
    struct Node *left, *right;
};
  
// Utility function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
  
// Utility function which
// returns whether the current node
// is a leaf or not
bool isleaf(Node *curr_node)
{
    return (curr_node->left == NULL &&
            curr_node->right == NULL);
}
  
// function to return the longest
// odd level depth if it exists
// otherwise 0
int deepestOddLevelDepthUtil(Node *curr_node, int curr_level)
{
    // Base case
    // return from here
    if ( curr_node == NULL)
        return 0;
  
    // increment current level
    curr_level += 1;
  
    // if curr_level is odd
    // and its a leaf node
    if ( curr_level % 2 != 0 && isleaf(curr_node))
        return curr_level;
  
    return max(deepestOddLevelDepthUtil(curr_node->left,curr_level),
               deepestOddLevelDepthUtil(curr_node->right,curr_level));
}
  
// A wrapper over deepestOddLevelDepth()
int deepestOddLevelDepth(Node *curr_node)
{
    return deepestOddLevelDepthUtil(curr_node, 0);
}
  
// Driver code
int main()
{
    /*   10
       /    
     28       13
            /    
          14       15
                  
                 23   24
    Let us create Binary Tree shown in above example */
    Node *root  = newNode(10);
    root->left  = newNode(28);
    root->right = newNode(13);
  
    root->right->left   = newNode(14);
    root->right->right  = newNode(15);
  
    root->right->right->left  = newNode(23);
    root->right->right->right = newNode(24);
  
  
    cout << deepestOddLevelDepth(root) << endl;
  
    return 0;
}

Java

// Java program to find depth of the deepest 
// odd level node 
class GfG { 
  
// A Tree node 
static class Node 
    int key; 
    Node left, right; 
  
// Utility function to create a new node 
static Node newNode(int key) 
    Node temp = new Node(); 
    temp.key = key; 
    temp.left = null;
    temp.right = null
    return (temp); 
  
// Utility function which 
// returns whether the current node 
// is a leaf or not 
static boolean isleaf(Node curr_node) 
    return (curr_node.left == null && curr_node.right == null); 
  
// function to return the longest 
// odd level depth if it exists 
// otherwise 0 
static int deepestOddLevelDepthUtil(Node curr_node, int curr_level) 
    // Base case 
    // return from here 
    if ( curr_node == null
        return 0
  
    // increment current level 
    curr_level += 1
  
    // if curr_level is odd 
    // and its a leaf node 
    if ( curr_level % 2 != 0 && isleaf(curr_node)) 
        return curr_level; 
  
    return Math.max(deepestOddLevelDepthUtil(curr_node.left,curr_level), 
                deepestOddLevelDepthUtil(curr_node.right,curr_level)); 
  
// A wrapper over deepestOddLevelDepth() 
static int deepestOddLevelDepth(Node curr_node) 
    return deepestOddLevelDepthUtil(curr_node, 0); 
  
public static void main(String[] args) 
    /* 10 
    /  
    28 13 
            /  
        14 15 
                /  
                23 24 
    Let us create Binary Tree shown in above example */
    Node root = newNode(10); 
    root.left = newNode(28); 
    root.right = newNode(13); 
  
    root.right.left = newNode(14); 
    root.right.right = newNode(15); 
  
    root.right.right.left = newNode(23); 
    root.right.right.right = newNode(24); 
  
  
    System.out.println(deepestOddLevelDepth(root)); 
}
  

Python3

# Python3 program to find depth of 
# the deepest odd level node
  
# Helper function that allocates a 
# new node with the given data and 
# None left and right poers.                                     
class newNode: 
  
    # Constructor to create a new node 
    def __init__(self, data): 
        self.data = data
        self.left = None
        self.right = None
  
# Utility function which returns 
# whether the current node is a 
# leaf or not 
def isleaf(curr_node) :
    return (curr_node.left == None and 
            curr_node.right == None
  
# function to return the longest 
# odd level depth if it exists 
# otherwise 0 
def deepestOddLevelDepthUtil(curr_node, 
                             curr_level) :
  
    # Base case 
    # return from here 
    if (curr_node == None) :
        return 0
  
    # increment current level 
    curr_level += 1
  
    # if curr_level is odd and
    # its a leaf node 
    if (curr_level % 2 != 0 and 
        isleaf(curr_node)) :
        return curr_level 
  
    return max(deepestOddLevelDepthUtil(curr_node.left, 
                                           curr_level),
               deepestOddLevelDepthUtil(curr_node.right, 
                                            curr_level)) 
  
# A wrapper over deepestOddLevelDepth() 
def deepestOddLevelDepth(curr_node) :
  
    return deepestOddLevelDepthUtil(curr_node, 0)
          
# Driver Code 
if __name__ == '__main__':
  
    """ 10 
    /      
    28     13 
            /      
        14     15 
                /  
                23 24 
    Let us create Binary Tree shown in
    above example """
    root = newNode(10
    root.left = newNode(28
    root.right = newNode(13
    root.right.left = newNode(14
    root.right.right = newNode(15)
    root.right.right.left = newNode(23)
    root.right.right.right = newNode(24)
    print(deepestOddLevelDepth(root)) 
  
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program to find depth of the deepest 
// odd level node 
using System;
  
class GfG 
  
    // A Tree node 
    class Node 
    
        public int key; 
        public Node left, right; 
    
  
    // Utility function to create a new node 
    static Node newNode(int key) 
    
        Node temp = new Node(); 
        temp.key = key; 
        temp.left = null;
        temp.right = null
        return (temp); 
    
  
    // Utility function which 
    // returns whether the current node 
    // is a leaf or not 
    static bool isleaf(Node curr_node) 
    
        return (curr_node.left == null && 
                curr_node.right == null); 
    
  
    // function to return the longest 
    // odd level depth if it exists 
    // otherwise 0 
    static int deepestOddLevelDepthUtil(Node curr_node,
                                        int curr_level) 
    
        // Base case 
        // return from here 
        if ( curr_node == null
            return 0; 
  
        // increment current level 
        curr_level += 1; 
  
        // if curr_level is odd 
        // and its a leaf node 
        if ( curr_level % 2 != 0 && isleaf(curr_node)) 
            return curr_level; 
  
        return Math.Max(deepestOddLevelDepthUtil(curr_node.left,curr_level), 
                    deepestOddLevelDepthUtil(curr_node.right,curr_level)); 
    
  
    // A wrapper over deepestOddLevelDepth() 
    static int deepestOddLevelDepth(Node curr_node) 
    
        return deepestOddLevelDepthUtil(curr_node, 0); 
    
  
    public static void Main(String[] args) 
    
        /* 10 
        /  
        28 13 
                /  
            14 15 
                    /  
                    23 24 
        Let us create Binary Tree shown in above example */
        Node root = newNode(10); 
        root.left = newNode(28); 
        root.right = newNode(13); 
  
        root.right.left = newNode(14); 
        root.right.right = newNode(15); 
  
        root.right.right.left = newNode(23); 
        root.right.right.right = newNode(24); 
  
  
        Console.WriteLine(deepestOddLevelDepth(root)); 
    }
  
// This code is contributed by PrinciRaj1992


Output:

3

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