Kth Employee Reached in an Ordered Hierarchy

Problem Statement

You are given a binary tree representing the organizational hierarchy of a company. Each node in the tree has a unique integer ID. An employee's 'rank' is determined by their position in an in-order traversal of the tree.

Your task is to implement a function that returns the ID of the k-th employee (1-indexed) in the in-order traversal of the hierarchy rooted at a given node. If the subtree contains fewer than k nodes, return -1.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def get_kth_employee(root: TreeNode, k: int) -> int:

Constraints

• The number of nodes n in the tree is up to 10^5.
• 1 <= k <= n.
• The tree structure is fixed for each query.

Examples

Example 1:

• Input: root = [3, 1, 4, null, 2], k = 2
• Tree structure: Node 3 has left child 1 and right child 4. Node 1 has right child 2.
• In-order traversal: [1, 2, 3, 4]
• Output: 2

Example 2:

• Input: root = [5, 3, 6], k = 4
• In-order traversal: [3, 5, 6]
• Output: -1

Edge Cases

• Tree with only one node.
• k being larger than the total number of nodes.
• A highly skewed tree (resembling a linked list).