findKthSymbol
that takes the current row number n
, the position k
, and the value of the root node rootVal
as arguments.n
is 1, return rootVal
as the base case.totalNodes = 2^(n - 1)
.k
is in the left or right half of the row. If k <= totalNodes / 2
, the target is in the left subtree; otherwise, it's in the right subtree.findKthSymbol(n - 1, k, rootVal)
recursively.k
to k - totalNodes / 2
and call findKthSymbol(n - 1, k, 1 - rootVal)
recursively.findKthSymbol(n, k, 0)
.