Question

The code should be in java.

Question: In an infinite binary tree where every node has two children, the nodes are labelled in row order. In each row, the labeling is left to right.

$CPT-287_-_Hybrid_-_Lecture_Assignment_6_-_Picture_2_-_PNG.png$

Given the label of a node in this tree, please write a method to return the labels in the path from the root of the tree to the node with that label. Your algorithm should have time complexity of $LaTeX: \color{blue}{O(\log{n})}$ O ( log ⁡ n ).

Example
Method Argument	8
Expected Method Return Value	[0, 1, 3, 8]

Answer 1

If you have any doubts regarding this question, please comment in the comment section, I am sure to help. If you like my answer. please up vote it, It will encourage me to answer more.

If you will draw the binary tree, you will see that the parent of a node labelled as "l " is (l-1)/2. For example, prent of node of label 8 is (8-1 )/2 =3, parent of 3 is (3-1)/2 = 1 and parent of 1 is (1-1)/2 = 0. So, just dividing the label minus one by 2 will give the parent node and we will reach the root and hence, we will get the path from root to that label .

Code for the above program is:-

import java.util.*;
public class TreeLabel
{

public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the label:- ");
int label = sc.nextInt();

ArrayList<Integer> labelList = new ArrayList<Integer>();
int x =label;
while(x!=0)
{
labelList.add(x);
x=(x-1)/2;
}
labelList.add(0); //"0" is always the root node.
Collections.reverse(labelList);
System.out.println(" Labels in the path from the root of the tree to the node with the label "+label+":- ");
System.out.println(labelList);
}
}

Code Snippet:-

import java.util.*; public class TreeLabel { public static void main(String args[]) Scanner sc = new Scanner (System.in); System.out.println("Enter the label:- "); int label = sc.nextInt (); labelList = new ArrayList<Integer>(); W NO 00 Join W NOCOWN ArrayList<Integer> int x =label; while (x!=0) labelList.add(x); x=(x-1)/2; labelList.add(0); //"0" is always the root node. Collections. reverse (labelList); System.out.println(" Labels in the path from the root of the tree to the node with the label "+label+":- "); System.out.println(labelList);

Output Snippet:-

C:\Users\Dell\Desktop>javac TreeLabel.java C:\Users\Dell\Desktop>java TreeLabel Enter the label:- Labels in the path from the root of the tree to the node with the label 8: - [1, 3, 8] C:\Users\Dell\Desktop>javac TreeLabel.java C:\Users\Dell\Desktop>java TreeLabel Enter the label:- Labels in the path from the root of the tree to the node with the label 8: - [0, 1, 3, 8] C:\Users\Dell\Desktop>java TreeLabel Enter the label:- Labels in the path from the root of the tree to the node with the label 26: - [@, 2, 5, 12, 26] C:\Users\Dell\Desktop>java TreeLabel Enter the label:- 25 Labels in the path from the root of the tree to the node with the label 25:- [@, 2, 5, 12, 25]

Following in above given figure is the output for the above code.