Company: Google
Position: SWE L3

Status: BTech - new graduate with 1 year exp.

Problem

Given a complete binary tree, for example:

       o
     /   \
   o       o
  / \     / \
 o   o   o   o
/ \
o o

Assume we number the nodes as follows:

       1
     /   \
   2       3
  / \     / \
 4   5   6   7
/ \
8 9

Write a function that takes the root pointer and a number from our indexing system above, and returns whether or not that node exists in the tree.

Follow-up: https://leetcode.com/problems/count-complete-tree-nodes

Note: Nodes do not store any value, we're supposed to infer the value from the position of the node.