Find n-th node in Preorder traversal of a Binary Tree

0 0 4 minutes read

Given a Binary tree and a number N, write a program to find the N-th node in the Preorder traversal of the given Binary tree.

Prerequisite: Tree Traversal

Examples:

Input:      N = 4
              11
            /   \
           21    31
         /   \
        41     51
Output: 51
Explanation: Preorder Traversal of given Binary Tree is 11 21 41 51 31, 
so 4th node will be 51.

Input:      N = 5
             25
           /    \
          20    30
        /    \ /   \
      18    22 24   32
Output: 30

The idea to solve this problem is to do preorder traversal of the given binary tree and keep track of the count of nodes visited while traversing the tree and print the current node when the count becomes equal to N.

Implementation:

C++

// C++ program to find n-th node of 
// Preorder Traversal of Binary Tree
#include <bits/stdc++.h>
using namespace std;
 
// Tree node
struct Node {
    int data;
    Node *left, *right;
};
 
// function to create new node
struct Node* createNode(int item)
{
    Node* temp = new Node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
 
    return temp;
}
 
// function to find the N-th node in the preorder
// traversal of a given binary tree
void NthPreordernode(struct Node* root, int N)
{
    static int flag = 0;
 
    if (root == NULL)
        return;
 
    if (flag <= N) {
        flag++;
 
        // prints the n-th node of preorder traversal
        if (flag == N)
            cout << root->data;
 
        // left recursion
        NthPreordernode(root->left, N);
 
        // right recursion
        NthPreordernode(root->right, N);
    }
}
 
// Driver code
int main()
{
    // construction of binary tree
    struct Node* root = createNode(25);
    root->left = createNode(20);
    root->right = createNode(30);
    root->left->left = createNode(18);
    root->left->right = createNode(22);
    root->right->left = createNode(24);
    root->right->right = createNode(32);
 
    // nth node
    int N = 6;
 
    // prints n-th  found
    NthPreordernode(root, N);
 
    return 0;
}

Java

// Java program to find n-th node of 
// Preorder Traversal of Binary Tree
class GFG
{
 
// Tree node
static class Node 
{
    int data;
    Node left, right;
};
 
// function to create new node
static Node createNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
static int flag = 0;
 
// function to find the N-th node in the preorder
// traversal of a given binary tree
static void NthPreordernode(Node root, int N)
{
     
 
    if (root == null)
        return;
 
    if (flag <= N)
    {
        flag++;
 
        // prints the n-th node of preorder traversal
        if (flag == N)
            System.out.print( root.data);
 
        // left recursion
        NthPreordernode(root.left, N);
 
        // right recursion
        NthPreordernode(root.right, N);
    }
}
 
// Driver code
public static void main(String args[])
{
    // construction of binary tree
    Node root = createNode(25);
    root.left = createNode(20);
    root.right = createNode(30);
    root.left.left = createNode(18);
    root.left.right = createNode(22);
    root.right.left = createNode(24);
    root.right.right = createNode(32);
 
    // nth node
    int N = 6;
 
    // prints n-th found
    NthPreordernode(root, N);
}
}
 
// This code contributed by Arnab Kundu

Python3

# Python program to find n-th node of 
# Preorder Traversal of Binary Tree
 
class createNode(): 
 
    def __init__(self, data): 
        self.data = data
        self.left = None
        self.right = None
         
         
# function to find the N-th node in the preorder 
# traversal of a given binary tree
flag = [0]
def NthPreordernode(root, N): 
    if (root == None):
        return
 
    if (flag[0] <= N): 
        flag[0] += 1
 
        # prints the n-th node of preorder traversal 
        if (flag[0] == N):
            print(root.data)
 
        # left recursion 
        NthPreordernode(root.left, N) 
 
        # right recursion 
        NthPreordernode(root.right, N)
         
# Driver code 
if __name__ == '__main__':
     
    # construction of binary tree 
    root = createNode(25) 
    root.left = createNode(20) 
    root.right = createNode(30) 
    root.left.left = createNode(18) 
    root.left.right = createNode(22) 
    root.right.left = createNode(24) 
    root.right.right = createNode(32) 
 
    # nth node 
    N = 6
 
    # prints n-th found  
    NthPreordernode(root, N)
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# program to find n-th node of 
// Preorder Traversal of Binary Tree 
using System;
     
class GFG
{
 
// Tree node
public class Node 
{
    public int data;
    public Node left, right;
};
 
// function to create new node
static Node createNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
static int flag = 0;
 
// function to find the N-th node in the preorder
// traversal of a given binary tree
static void NthPreordernode(Node root, int N)
{
     
 
    if (root == null)
        return;
 
    if (flag <= N)
    {
        flag++;
 
        // prints the n-th node of preorder traversal
        if (flag == N)
            Console.Write( root.data);
 
        // left recursion
        NthPreordernode(root.left, N);
 
        // right recursion
        NthPreordernode(root.right, N);
    }
}
 
// Driver code
public static void Main(String []args)
{
    // construction of binary tree
    Node root = createNode(25);
    root.left = createNode(20);
    root.right = createNode(30);
    root.left.left = createNode(18);
    root.left.right = createNode(22);
    root.right.left = createNode(24);
    root.right.right = createNode(32);
 
    // nth node
    int N = 6;
 
    // prints n-th found
    NthPreordernode(root, N);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript program to find n-th node of 
// Preorder Traversal of Binary Tree 
 
// Tree node
class Node 
{
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
 
// function to create new node
function createNode(item)
{
    var temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
 
var flag = 0;
 
// function to find the N-th node in the preorder
// traversal of a given binary tree
function NthPreordernode(root, N)
{
     
 
    if (root == null)
        return;
 
    if (flag <= N)
    {
        flag++;
 
        // prints the n-th node of preorder traversal
        if (flag == N)
            document.write( root.data);
 
        // left recursion
        NthPreordernode(root.left, N);
 
        // right recursion
        NthPreordernode(root.right, N);
    }
}
 
// Driver code
// construction of binary tree
var root = createNode(25);
root.left = createNode(20);
root.right = createNode(30);
root.left.left = createNode(18);
root.left.right = createNode(22);
root.right.left = createNode(24);
root.right.right = createNode(32);
 
// nth node
var N = 6;
 
// prints n-th found 
NthPreordernode(root, N);
 
// This code is contributed by famously.
</script>

Output

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in the given binary tree.
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!