Finding Minimum Steps in Special Binary Tree
Given two integer values (i and j) as input representing two nodes of a special binary tree. The special binary tree has this property that the root node’s value is always 1 and for every node, its left child will be the node’s value * 3, and the right child will be ( node’s value * 3) + 1. The given integer values exist in the tree then find the minimum steps required to reach the other node. By moving one step you can either move one level up or go one level down.
Examples:
Input: i = 1, j = 3
Output: 1
Explanation: The tree for the above input will be1
/ \
3 4The difference between levels of 1 and 3 is 1 so it will take 1 step.
Input: i = 1, j = 39
Output: 3
Explanation: The tree for the above input will be1
/ \
3 4
/ \ / \
9 10 12 13
/ \ / \ / \ / \
27 28 30 31 36 37 38 39Here the difference between level of 1 and 39 is 3 so it will take 3 steps.
Intuition: To solve the problem follow the below idea:
Start generating the tree with the mentioned property until we encounter both the nodes and as soon as we found both the nodes then find level of both nodes and return absolute difference between them.
Approach: Follow the below steps:
We will use a 2D Vector for constructing the binary tree and the row of 2D vector will represent level of current row so it will be easy for further calculation. Initialize three variables ithRow = -1 , jthRow = -1 and row = 0, along with a 2D vector arr with value 1. Now run a while loop till ithRow == – 1 and jthRow == -1 and repeat the below mentioned steps for every iteration. NOTE: i and j are input values.
- Run a while loop till row<i or row<j and initialize a vector temp.
- Now iterate over the previous row of 2D vector arr using a for loop and calculate child’s values using the formula mentioned in question.
- If child1’s or child2’s value matches input value then update respective row tracking variables i.e. ithRow and jthRow .
- After this push child1 and child2 in temp vector then push temp vector in 2D vector arr and increment row count.
- Then check whether we have found both the values if yes then break the loop.
- At last return the absolute difference between ithRow and jthRow.
Below Code is the implementation of above approach in CPP.
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
int findMinimumSteps(int i, int j)
{
// Two variables for tracking level of
// input variables and row for maintaining
// row details
int ithRow = -1, jthRow = -1, row = 0;
// 2D vector to create tree
vector<vector<int> > arr;
arr.push_back({ 1 });
while (ithRow == -1 && jthRow == -1) {
while (row < i || row < j) {
// Variable for storing
// children of previous row
vector<int> temp;
for (int k = 0; k < arr[row].size(); k++) {
// Calculating child's values as
// given in question
int child1 = arr[row][i] * 3;
int child2 = (arr[row][i] * 3) + 1;
// Checking whether any child's
// value matches given input if
// yes then update respective
// row tracker
if (child1 == i)
ithRow = row + 1;
if (child2 == i)
ithRow = row + 1;
if (child1 == j)
jthRow = row + 1;
if (child2 == j)
jthRow = row + 1;
// Pushing both childs into vector
temp.push_back(child1);
temp.push_back(child2);
}
// Insert new row so count
// will be increased
row++;
// push the calculated
// childs in the 2D vector
arr.push_back(temp);
// if both values are found then
// break the loop
if (ithRow != -1 && jthRow != -1)
break;
}
}
// Returning the absolute
// difference between the level of
// given two input nodes
return abs(ithRow - jthRow);
}
// Drivers code
int main()
{
int i = 1;
int j = 3;
// Function call
cout << findMinimumSteps(i, j);
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class MinimumSteps {
static int findMinimumSteps(int i, int j) {
int ithRow = -1, jthRow = -1, row = 0;
// 2D list to create a tree
List<List<Integer>> arr = new ArrayList<>();
arr.add(List.of(1));
while (ithRow == -1 && jthRow == -1) {
while (row < i || row < j) {
// List for storing children of the previous row
List<Integer> temp = new ArrayList<>();
for (int k = 0; k < arr.get(row).size(); k++) {
// Calculating child's values as given in the question
int child1 = arr.get(row).get(k) * 3;
int child2 = arr.get(row).get(k) * 3 + 1;
// Checking whether any child's value matches the given input
// If yes, then update the respective row tracker
if (child1 == i) ithRow = row + 1;
if (child2 == i) ithRow = row + 1;
if (child1 == j) jthRow = row + 1;
if (child2 == j) jthRow = row + 1;
// Pushing both children into the list
temp.add(child1);
temp.add(child2);
}
// Inserting a new row so the count will be increased
row++;
// Pushing the calculated children into the 2D list
arr.add(new ArrayList<>(temp));
// If both values are found, then break the loop
if (ithRow != -1 && jthRow != -1) break;
}
}
// Returning the absolute difference between the levels of the given two input nodes
return Math.abs(ithRow - jthRow)-1;
}
// Driver code
public static void main(String[] args) {
int i = 1;
int j = 3;
// Function call
System.out.println(findMinimumSteps(i, j));
}
}
def find_minimum_steps(i, j):
# Function to calculate the level of a given node in the tree
def calculate_level(node):
level = 0
while node > 1:
if node % 3 == 0:
node //= 3
else:
node = (node - 1) // 3
level += 1
return level
# Calculate levels for both input nodes
ith_level = calculate_level(i)
jth_level = calculate_level(j)
# Return the absolute difference between the levels
return abs(ith_level - jth_level)
if __name__ == "__main__":
i = 1
j = 3
# Function call
print(find_minimum_steps(i, j))
using System;
using System.Collections.Generic;
class Program
{
// Function to find the minimum steps between two nodes in a tree
static int FindMinimumSteps(int i, int j)
{
// Variables to track the level of input nodes
int ithRow = -1, jthRow = -1, row = 0;
// 2D list to represent the tree
List<List<int>> arr = new List<List<int>>();
arr.Add(new List<int> { 1 }); // Initial row with root node value 1
// Continue until both nodes are found in the tree
while (ithRow == -1 && jthRow == -1)
{
// Process each node in the current row
while (row < i || row < j)
{
List<int> temp = new List<int>();
for (int k = 0; k < arr[row].Count; k++)
{
// Calculate children values based on the given formula
int child1 = arr[row][k] * 3;
int child2 = (arr[row][k] * 3) + 1;
// Check if any child's value matches the input nodes
if (child1 == i)
ithRow = row + 1;
if (child2 == i)
ithRow = row + 1;
if (child1 == j)
jthRow = row + 1;
if (child2 == j)
jthRow = row + 1;
// Add both children to the temporary list
temp.Add(child1);
temp.Add(child2);
}
// Move to the next row
row++;
// Add the calculated children to the 2D list
arr.Add(new List<int>(temp));
// If both values are found, break the loop
if (ithRow != -1 && jthRow != -1)
break;
}
}
// Return the absolute difference between the levels of the two input nodes
return Math.Abs(ithRow - jthRow + 1) ;
}
// Main method to test the FindMinimumSteps function
static void Main()
{
int i = 1;
int j = 3;
// Call the function and print the result
Console.WriteLine(FindMinimumSteps(i, j));
}
}
function findMinimumSteps(i, j) {
let ithRow = -1, jthRow = -1, row = 0;
// 2D array to create a tree
let arr = [[]];
arr[0] = [1];
while (ithRow === -1 && jthRow === -1) {
while (row < i || row < j) {
// Array for storing children of the previous row
let temp = [];
for (let k = 0; k < arr[row].length; k++) {
// Calculating child's values as given in the question
let child1 = arr[row][k] * 3;
let child2 = arr[row][k] * 3 + 1;
// Checking whether any child's value matches the given input
// If yes, then update the respective row tracker
if (child1 === i) ithRow = row + 1;
if (child2 === i) ithRow = row + 1;
if (child1 === j) jthRow = row + 1;
if (child2 === j) jthRow = row + 1;
// Pushing both children into the array
temp.push(child1);
temp.push(child2);
}
// Inserting a new row so the count will be increased
row++;
// Pushing the calculated children into the 2D array
arr.push([...temp]);
// If both values are found, then break the loop
if (ithRow !== -1 && jthRow !== -1) break;
}
}
// Returning the absolute difference between the levels of the given two input nodes
return Math.abs(ithRow - jthRow) - 1;
}
// Driver code
let i = 1;
let j = 3;
// Function call
console.log(findMinimumSteps(i, j));
Output
1
Time Complexity: O(i*j)
Auxiliary Space: O((max(i, j)/3)^2)
Contact Us