# Search in a Virtually Complete Binary Tree

Consider a complete binary tree of `n`

nodes whose values are `1`

to `n`

. The root has value of `1`

, its left child is `2`

and its right child is `3`

. In general, nodes’ values are labelled `1`

to `n`

in level order traversal.

You are given a binary tree `root`

and an integer `target`

. Given that the `root`

was originally a complete binary tree whose values were labelled as described above, and that some of the subtrees were deleted, return whether `target`

exists in `root`

.

Bonus: solve in \(\mathcal{O}(h)\) time where `h`

is the height of the tree.

**Constraints**

`1 ≤ n ≤ 100,000`

where`n`

is the number of nodes in`root`

https://binarysearch.com/problems/Search-in-a-Virtually-Complete-Binary-Tree

## Examples

### Example 1

**Input**

- root =

- target =
`7`

**Output**

- answer =
`False`

**Explanation**

`7`

does not exist in this tree.

### Example 2

**Input**

- root =

- target =
`6`

**Output**

- answer =
`True`

**Explanation**

`6`

exists in this tree.

## Leave a comment