Given an integer ‘K’ and a binary tree in string format. Every node of a tree has value in range from 0 to 9. We need to find product of elements at K-th level from root. The root is at level 0.
Note : Tree is given in the form: (node value(left subtree)(right subtree))
Examples:
Input : tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"
k = 2
Output : 72
Its tree representation is shown below
Elements at level k = 2 are 6, 4, 1, 3
sum of the digits of these elements = 6 * 4 * 1 * 3 = 72
Input : tree = "(8(3(2()())(6(5()())()))(5(10()())(7(13()())())))"
k = 3
Output : 15
Elements at level k = 3 are 5, 1 and 3
sum of digits of these elements = 5 * 1 * 3 = 15
Approach :
- Input ‘tree’ in string format and level k
- Initialize level = -1 and product = 1
- for each character ‘ch’ in ‘tree’
3.1 if ch == ‘(‘ then
–> level++
3.2 else if ch == ‘)’ then
–> level–
3.3 else
if level == k then
product = product * (ch-‘0’)- 4. Print product
Implementation:
C++
// C++ implementation to find product of// digits of elements at k-th level#include <bits/stdc++.h>using namespace std;// Function to find product of digits// of elements at k-th levelint productAtKthLevel(string tree, int k){ int level = -1; int product = 1; // Initialize result int n = tree.length(); for (int i = 0; i < n; i++) { // increasing level number if (tree[i] == '(') level++; // decreasing level number else if (tree[i] == ')') level--; else { // check if current level is // the desired level or not if (level == k) product *= (tree[i] - '0'); } } // required product return product;}// Driver programint main(){ string tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"; int k = 2; cout << productAtKthLevel(tree, k); return 0;} |
Java
// Java implementation to find product of// digits of elements at k-th levelclass GFG{ // Function to find product of digits // of elements at k-th level static int productAtKthLevel(String tree, int k) { int level = -1; // Initialize result int product = 1; int n = tree.length(); for (int i = 0; i < n; i++) { // increasing level number if (tree.charAt(i) == '(') level++; // decreasing level number else if (tree.charAt(i) == ')') level--; else { // check if current level is // the desired level or not if (level == k) product *= (tree.charAt(i) - '0'); } } // required product return product; } // Driver program public static void main(String[] args) { String tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"; int k = 2; System.out.println(productAtKthLevel(tree, k)); }}// This code is contributed // by Smitha Dinesh Semwal. |
Python3
# Python 3 implementation# to find product of# digits of elements# at k-th level# Function to find# product of digits# of elements at# k-th leveldef productAtKthLevel(tree, k): level = -1 # Initialize result product = 1 n = len(tree) for i in range(0, n): # increasing level number if (tree[i] == '('): level+=1 # decreasing level number elif (tree[i] == ')'): level-=1 else: # check if current level is # the desired level or not if (level == k): product *= (int(tree[i]) - int('0')) # required product return product# Driver programtree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"k = 2print(productAtKthLevel(tree, k))# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# implementation to find // product of digits of// elements at k-th levelusing System;class GFG{ // Function to find product // of digits of elements // at k-th level static int productAtKthLevel(string tree, int k) { int level = -1; // Initialize result int product = 1; int n = tree.Length; for (int i = 0; i < n; i++) { // increasing // level number if (tree[i] == '(') level++; // decreasing // level number else if (tree[i] == ')') level--; else { // check if current level is // the desired level or not if (level == k) product *= (tree[i] - '0'); } } // required product return product; } // Driver Code static void Main() { string tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"; int k = 2; Console.WriteLine(productAtKthLevel(tree, k)); }}// This code is contributed by Sam007 |
PHP
<?php// php implementation to find product of// digits of elements at k-th level// Function to find product of digits// of elements at k-th levelfunction productAtKthLevel($tree, $k){ $level = -1; $product = 1; // Initialize result $n = strlen($tree); for ($i = 0; $i < $n; $i++) { // increasing level number if ($tree[$i] == '(') $level++; // decreasing level number else if ($tree[$i] == ')') $level--; else { // check if current level is // the desired level or not if ($level == $k) $product *= (ord($tree[$i]) - ord('0')); } } // required product return $product;} // Driver Code $tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"; $k = 2; echo productAtKthLevel($tree, $k);//This code is contributed by mits ?> |
Javascript
<script> // Javascript implementation to find // product of digits of // elements at k-th level // Function to find product // of digits of elements // at k-th level function productAtKthLevel(tree, k) { let level = -1; // Initialize result let product = 1; let n = tree.length; for (let i = 0; i < n; i++) { // increasing // level number if (tree[i] == '(') level++; // decreasing // level number else if (tree[i] == ')') level--; else { // check if current level is // the desired level or not if (level == k) product *= (tree[i].charCodeAt() - '0'.charCodeAt()); } } // required product return product; } let tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"; let k = 2; document.write(productAtKthLevel(tree, k)); </script> |
Output
72
Time Complexity: O(n)
Auxiliary Space: O(1)
Please suggest if someone has a better solution which is more efficient in terms of space and time.
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!
