Given a binary tree and an integer X, the task is to find out all the occurrences of X in the given tree, and print its level and its position from left to right on that level. If X is not found, print -1.
Examples:
Input: X=35
10
/ \
20 30
/ \ / \
40 60 35 50
Output: [(3, 3)]
Explanation: Integer X=35 is present in level 3 and its position is 3 from left.Input: X= 2
1
/ \
2 3
/ \ / \
4 6 8 2
Output: [(2, 1), (3, 4)]
Explanation: Integer X=2 is present in level 2 and its position is 1 from left also it is present in level 3 and position from left is 4.
Approach: This problem can be solved using level order traversal of binary tree using queue.
- Perform level order traversal of given Binary Tree using Queue.
- Keep track of level count and the count of nodes from left to right during traversal
- Whenever X is encountered during traversal, print or store the level count and position of current occurrence of X.
Below is the implementation of the above approach:
C++
// C++ program to print level and// position of Node X in binary tree#include <bits/stdc++.h>using namespace std;// A Binary Tree Nodestruct Node { int data; struct Node *left, *right;};// Function to find and print// level and position of node Xvoid printLevelandPosition(Node* root, int X){ // Base Case if (root == NULL) return; // Create an empty queue queue<Node*> q; // Enqueue Root and initialize height q.push(root); // Create and initialize current // level and position by 1 int currLevel = 1, position = 1; while (q.empty() == false) { int size = q.size(); while (size--) { Node* node = q.front(); // print if node data equal to X if (node->data == X) cout << "(" << currLevel << " " << position << "), "; q.pop(); // increment the position position++; // Enqueue left child if (node->left != NULL) q.push(node->left); // Enqueue right child if (node->right != NULL) q.push(node->right); } // increment the level currLevel++; position = 1; }}// Utility function to create a new tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp;}// Driver program to test above functionsint main(){ // Let us create binary tree Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(2); int X = 2; printLevelandPosition(root, X); return 0;} |
Java
// JAVA program to print level and// position of Node X in binary treeimport java.util.*;// A Binary Tree Nodeclass Node { int data; Node left; Node right;}class GFG{ // Function to find and print // level and position of node X public static void printLevelandPosition(Node root, int X) { // Base Case if (root == null) return; // Create an empty queue Queue<Node> q = new LinkedList<>(); // Enqueue Root and initialize height q.add(root); // Create and initialize current // level and position by 1 int currLevel = 1, position = 1; while (q.size() != 0) { int size = q.size(); while ((size--) != 0) { Node node = q.peek(); // print if node data equal to X if (node.data == X) System.out.print("(" + currLevel + " " + position + "), "); q.remove(); // increment the position position++; // Enqueue left child if (node.left != null) q.add(node.left); // Enqueue right child if (node.right != null) q.add(node.right); } // increment the level currLevel++; position = 1; } } // Utility function to create a new tree node public static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp; } // Driver program to test above functions public static void main(String[] args) { // Let us create binary tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(2); int X = 2; printLevelandPosition(root, X); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approachclass Node: def __init__(self,d): self.data = d self.left = None self.right = None # Function to find and print# level and position of node Xdef printLevelandPosition(root, X): # Base Case if (root == None): return # Create an empty queue q = [] # Enqueue Root and initialize height q.append(root) # Create and initialize current # level and position by 1 currLevel,position = 1,1 while (len(q) != 0): size = len(q) while (size != 0): node = q[0] q = q[1:] # print if node data equal to X if (node.data == X): print (f"({currLevel} {position}),",end =" ") # increment the position position += 1 # Enqueue left child if (node.left != None): q.append(node.left) # Enqueue right child if (node.right != None): q.append(node.right) size -= 1 # increment the level currLevel += 1 position = 1# Driver program to test above functions# Let us create binary treeroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(2)X = 2printLevelandPosition(root, X)# This code is contributed by shinjanpatra |
C#
// C# program to print level and// position of Node X in binary treeusing System;using System.Collections.Generic;// A Binary Tree Nodepublic class Node { public int data; public Node left; public Node right;}public class GFG { // Function to find and print // level and position of node X public static void printLevelandPosition(Node root, int X) { // Base Case if (root == null) return; // Create an empty queue Queue<Node> q = new Queue<Node>(); // Enqueue Root and initialize height q.Enqueue(root); // Create and initialize current // level and position by 1 int currLevel = 1, position = 1; while (q.Count != 0) { int size = q.Count; while ((size--) != 0) { Node node = q.Peek(); // print if node data equal to X if (node.data == X) Console.Write("(" + currLevel + " " + position + "), "); q.Dequeue(); // increment the position position++; // Enqueue left child if (node.left != null) q.Enqueue(node.left); // Enqueue right child if (node.right != null) q.Enqueue(node.right); } // increment the level currLevel++; position = 1; } } // Utility function to create a new tree node public static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp; } // Driver program to test above functions public static void Main(String[] args) { // Let us create binary tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(2); int X = 2; printLevelandPosition(root, X); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code for the above approach class Node { constructor(d) { this.data = d; this.left = null; this.right = null; } } // Function to find and print // level and position of node X function printLevelandPosition(root, X) { // Base Case if (root == null) return; // Create an empty queue let q = []; // Enqueue Root and initialize height q.push(root); // Create and initialize current // level and position by 1 let currLevel = 1, position = 1; while (q.length != 0) { let size = q.length; while (size-- != 0) { let node = q.shift(); // print if node data equal to X if (node.data == X) document.write("(" + currLevel + " " + position + "), "); // increment the position position++; // Enqueue left child if (node.left != null) q.push(node.left); // Enqueue right child if (node.right != null) q.push(node.right); } // increment the level currLevel++; position = 1; } } // Driver program to test above functions // Let us create binary tree let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(2); let X = 2; printLevelandPosition(root, X); // This code is contributed by Potta Lokesh </script> |
Output
(2 1), (3 2),
Time Complexity: O(n)
Auxiliary Space : O(n)
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!
