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 nodestruct Node { int data; Node *left, *right;};// function to create new nodestruct 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 treevoid 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 codeint 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 Treeclass GFG{// Tree nodestatic class Node { int data; Node left, right;};// function to create new nodestatic 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 treestatic 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 codepublic 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 Treeclass 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 treeflag = [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 nodepublic class Node { public int data; public Node left, right;};// function to create new nodestatic 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 treestatic 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 codepublic 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 nodeclass Node { constructor() { this.data = 0; this.left = null; this.right = null; }};// function to create new nodefunction 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 treefunction 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 treevar 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 nodevar N = 6;// prints n-th found NthPreordernode(root, N);// This code is contributed by famously.</script> |
Output
24
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
