Leetcode Problem 779. K-th Symbol in Grammar

779. K-th Symbol in Grammar

Leetcode Solutions

Approach: Binary Tree Traversal

  1. Define a recursive function findKthSymbol that takes the current row number n, the position k, and the value of the root node rootVal as arguments.
  2. If n is 1, return rootVal as the base case.
  3. Calculate the total number of nodes in the current row as totalNodes = 2^(n - 1).
  4. Determine if 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.
  5. If the target is in the left subtree, call findKthSymbol(n - 1, k, rootVal) recursively.
  6. If the target is in the right subtree, update k to k - totalNodes / 2 and call findKthSymbol(n - 1, k, 1 - rootVal) recursively.
  7. The initial call is made with findKthSymbol(n, k, 0).
UML Thumbnail

Approach: Normal Recursion

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...