AlgoDesign

Kth node inorder traversal

1class Solution:
2    def kthNodeInorderTraversal(self, root, k):
3        while root:
4            leftSize = root.left.size if root.left else 0
5            if leftSize + 1 < k:
6                k -= leftSize + 1
7                root = root.right
8            elif leftSize + 1 == k: return root
9            else: root = root.left
10        
11        return None