DEV Community

Discussion on: Kth Smallest Element in a BST, solving Netflix Interview question.

View post
Collapse
 
ayanb profile image
Ayan Banerjee • • Edited

You can also perform iterative inorder traversal and improve the time complexity to O(H + K). For a balanced tree H = logN however, for a skewed tree, it can be H = N.

def kthSmallest(root, k):
    s = []  # stack
    while root != None or s:
        while root != None:
            s.append(root)
            root = root.left
        root = s[-1]
        s.pop()
        k -= 1
        if k == 0: return root.val
        root = root.right
Collapse
 
akhilpokle profile image
Akhil •

Thanks for sharing :)