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)

var k_dup int
var res int

func kthSmallest(root *TreeNode, k int) int {
    k_dup = k
    inorder(root)
    return res
}

func inorder(node *TreeNode) {
    if node == nil {
        return
    }
    inorder(node.Left)
    k_dup -= 1
    if k_dup == 0 {
        res = node.Val
        return
    }
    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)

var k_dup int
var res int

func kthLargest(root *TreeNode, k int) int {
    k_dup = k
    inorder(root)
    return res
}

func inorder(node *TreeNode) {
    if node == nil {
        return
    }
    inorder(node.Right)
    k_dup -= 1
    if k_dup == 0 {
        res = node.Val
        return
    }
    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)

func findTarget(root *TreeNode, k int) bool {
    return helper(root, map[int]bool{}, k)
}

func helper(node *TreeNode, seen map[int]bool, k int) bool {
    if node == nil {
        return false
    }
    if seen[k-node.Val] {
        return true
    }
    seen[node.Val] = true
    return helper(node.Left, seen, k) || helper(node.Right, seen, k)
}

💻

---

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)

type BSTIterator struct {
    InorderArr []int
    CurrInd    int
}

func Constructor(root *TreeNode) BSTIterator {
    obj := BSTIterator{CurrInd: -1}
    inorder(root, &obj)
    return obj
}

func inorder(node *TreeNode, obj *BSTIterator) {
    if node == nil {
        return
    }
    inorder(node.Left, obj)
    obj.InorderArr = append(obj.InorderArr, node.Val)
    inorder(node.Right, obj)
}

func (this *BSTIterator) Next() int {
    this.CurrInd += 1
    return this.InorderArr[this.CurrInd]
}

func (this *BSTIterator) HasNext() bool {
    return this.CurrInd+1 < len(this.InorderArr)
}

💻

---