Given a complete(virtual) binary tree, return true/false if the given target node exists in the tree or not.
Here, the “virtual” means the tree nodes are numbered assuming the tree is a complete binary tree.
For example:
1
/ \
2 3
/ \ / \
4 (5)nil 6 (7)nil
//function signature
// bool doesNodeExist(root *TreeNode, target int)
doesNodeExist(root, 4) -> true
doesNodeExist(root, 7) -> false, Given the node on #7 is a nil node.
//Level order traversal solution, numbering the left(2n+1) and right(2n+2) children node is a trivial solution(time O(n)/O(target) and space O(n)/O(target)).
//Think of a better solution.
My solution using binary string:
Binary String represents the path from root to the node, where ‘1’ means going right and ‘0’ means going left.
For example, 4 = “100”, starting from the index 1, we go from root = 1, going left --> 2, going left --> 4;
7 = “111”, starting from index 1, we go from root = 1, going right --> 3, going right --> 7.
public boolean doesNodeExist(TreeNode root, int id) {
if (id <= 0) return false;
char[] binary = Integer.toBinaryString(id).toCharArray();
for (int i = 1; i < binary.length; i++) {
if (root == null) return false;
if (binary[i] == '0') root = root.left;
else root = root.right;
}
return root != null;
}