Part2

Floor in a BST

class Solution:
    def floor(self, root, X):
        node = root
        res = -1

        while node:
            if node.data == X:
                return node.data
            elif node.data < X:
                res = max(res, node.data)
                node = node.right
            else:
                node = node.left

        return res

💻

---

Ceil in a BST

class Solution:
    def findCeil(self, root, X):
        res = float("inf")
        node = root

        while node:
            if node.key == X:
                return node.key

            elif node.key > X:
                res = min(res, node.key)
                node = node.left

            else:
                node = node.right

        return res if res != float("inf") else -1

💻

---

Find K-th smallest element in BST

Example:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.k = k
        self.res = None
        self.inorder(root)
        return self.res

    def inorder(self, node):
        if not node:
            return

        self.inorder(node.left)
        self.k -= 1
        if not self.k:
            self.res = node.val
            return
        self.inorder(node.right)

💻

---

Find K-th largest element in BST

class Solution:
    def kthLargest(self, root, k):
        self.k = k
        self.res = None
        self.inorder(root)
        return self.res

    def inorder(self, node):
        if not node:
            return

        self.inorder(node.right)
        self.k -= 1
        if not self.k:
            self.res = node.data
            return
        self.inorder(node.left)

💻

---

Find a pair with a given sum in BST

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        self.k = k
        return self.helper(root, set())

    def helper(self, node, seen):
        if not node:
            return False

        if self.k - node.val in seen:
            return True

        seen.add(node.val)
        return self.helper(node.left, seen) or self.helper(node.right, seen)

💻

---

BST iterator

Refer leetcode link for problem description

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.inorder_arr = []
        self._inorder(root)
        self.curr_ind = -1

    def next(self) -> int:
        self.curr_ind += 1
        return self.inorder_arr[self.curr_ind]

    def hasNext(self) -> bool:
        return (self.curr_ind + 1) < len(self.inorder_arr)

    def _inorder(self, node):
        if not node:
            return
        self._inorder(node.left)
        self.inorder_arr.append(node.val)
        self._inorder(node.right)

💻

---