Problem
There is a complete binary tree with just value 0 or 1, the left child value is the same as parent value, the right child is NOT. Given a node which is on n level and k index, return the value of it.0 (1,1)
/ \
0 1 (2,1; 2,2)
/ \ / \
0 1 1 0 (3,1; 3,2; 3,3; 3,4)
For example, given n = 3, k = 2, the value is 1.
(2, 1) value is 0, (3,3) value is 1.
Solution
We can do binary tree level traversal with the aid of a queue, for level n, we need to poll pow(2, n-1) -1 number of nodes before starting to offer level n nodes to the queue. Then after poll k nodes, the answer is found. The time cost is O(2^n), the space cost is O(2^(n-1)) for the max queue size.
import java.util.*;
class ZeroOrOne {
public static int getLevelAndIndexVal(int n, int k) {//3 2
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
int limit = (int)Math.pow(2, n-1) - 1 + k;
int counter = 0;
while(!queue.isEmpty()) {
counter++;
int i = queue.poll();
if(counter == limit) return i;
queue.offer(i);
queue.offer(i == 0 ? 1:0);
}
return 100;
}
public static void main(String...args) {
System.out.println(getLevelAndIndexVal(3, 2));
}
}
class ZeroOrOne {
public static int getLevelAndIndexVal(int n, int k) {//3 2
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
int limit = (int)Math.pow(2, n-1) - 1 + k;
int counter = 0;
while(!queue.isEmpty()) {
counter++;
int i = queue.poll();
if(counter == limit) return i;
queue.offer(i);
queue.offer(i == 0 ? 1:0);
}
return 100;
}
public static void main(String...args) {
System.out.println(getLevelAndIndexVal(3, 2));
}
}
Another approach is to use bottom up recursion. We start at (n, k), recursively find the parent node, which is (n - 1, (k+1)/2).
Once n = 1, the root is found, the function recursively return the current node value as parent value to the caller, the caller can calculate its own value according to the parent value and its own index. Then recursively return itself to the calling children node.
class ZeroOrOne {
public static int findNode(int n, int k) {//3 2
if(n == 1) return k-1; //root
int parent = findNode(n-1, (k+1)/2);
if(k%2 != 0) return parent;
else return parent == 0 ? 1 : 0;
}
public static void main(String...args) {
System.out.println(findNode(3, 2));
}
}
public static int findNode(int n, int k) {//3 2
if(n == 1) return k-1; //root
int parent = findNode(n-1, (k+1)/2);
if(k%2 != 0) return parent;
else return parent == 0 ? 1 : 0;
}
public static void main(String...args) {
System.out.println(findNode(3, 2));
}
}
We recursively called n times to reach the root, then recursively returns n layer to reach the leaf. The time complexity is O(n). The space complexity is O(n), proportional to the layer of caller stack.
