Binary Search Tree

Table of Contents

• 530. Minimum Absolute Difference in BST (Easy)
• 230. Kth Smallest Element in a BST (Medium)
• 98. Validate Binary Search Tree (Medium)

530. Minimum Absolute Difference in BST

• LeetCode | 力扣

• Tags: Tree, Depth First Search, Breadth First Search, Binary Search Tree, Binary Tree

Python

from typing import Optional

from binarytree import build


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


def getMinimumDifference(root: Optional[TreeNode]) -> int:
    res = float("inf")
    pre = float("-inf")

    def dfs(node):  # inorder traversal
        if not node:
            return

        dfs(node.left)

        nonlocal res, pre
        res = min(res, node.val - pre)
        pre = node.val

        if res == 1:  # the minimum possible difference
            return

        dfs(node.right)

    dfs(root)

    return res


if __name__ == "__main__":
    root = [4, 2, 6, 1, 3]
    root = build(root)
    print(root)
    #     __4
    #    /   \
    #   2     6
    #  / \
    # 1   3
    assert getMinimumDifference(root) == 1

230. Kth Smallest Element in a BST

• LeetCode | 力扣

• Tags: Tree, Depth First Search, Binary Search Tree, Binary Tree

Python

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# Recursive
def kthSmallestRecursive(root: Optional[TreeNode], k: int) -> int:
    inorder = []

    def dfs(node):
        if not node:
            return None
        dfs(node.left)
        inorder.append(node.val)
        dfs(node.right)

    dfs(root)
    return inorder[k - 1]


# Iteratve
def kthSmallestIteratve(root: Optional[TreeNode], k: int) -> int:
    stack = []
    while True:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if not k:
            return root.val
        root = root.right


if __name__ == "__main__":
    root = build([3, 1, 4, None, 2])
    k = 1
    assert kthSmallestRecursive(root, k) == 1
    assert kthSmallestIteratve(root, k) == 1

98. Validate Binary Search Tree

• LeetCode | 力扣

• Tags: Tree, Depth First Search, Binary Search Tree, Binary Tree

PythonCPP

from itertools import pairwise
from math import inf
from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


def isValidBST1(root: Optional[TreeNode]) -> bool:
    inorder = []  # inorder traversal

    def dfs(node):
        if not node:
            return None
        dfs(node.left)
        inorder.append(node.val)
        dfs(node.right)

    dfs(root)

    for a, b in pairwise(inorder):
        if a >= b:
            return False

    return True


def isValidBST2(root: Optional[TreeNode]) -> bool:
    if not root:
        return True
    pre = -inf

    def dfs(node):
        if not node:
            return True
        if not dfs(node.left):
            return False

        nonlocal pre
        if node.val <= pre:
            return False
        pre = node.val

        return dfs(node.right)

    return dfs(root)


if __name__ == "__main__":
    root = [5, 1, 4, None, None, 3, 6]
    root = build(root)
    print(root)
    #   5__
    #  /   \
    # 1     4
    #      / \
    #     3   6
    assert not isValidBST1(root)  # [1, 5, 3, 4, 6]
    assert not isValidBST2(root)  # [1, 5, 3, 4, 6]

#include <cassert>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

class Solution {
   private:
    vector<int> inorder;
    bool check(vector<int> inorder) {
        int n = inorder.size();
        if (n <= 1) return true;
        for (int i = 1; i < n; i++) {
            if (inorder[i] <= inorder[i - 1]) return false;
        }
        return true;
    }

   public:
    bool isValidBST(TreeNode *root) {
        auto dfs = [&](auto &&self, TreeNode *node) -> void {
            if (!node) return;

            self(self, node->left);
            inorder.push_back(node->val);
            self(self, node->right);
        };

        dfs(dfs, root);

        return check(inorder);
    }
};

int main() {
    Solution s;
    TreeNode *root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    assert(s.isValidBST(root) == true);

    root = new TreeNode(5);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->right->left = new TreeNode(3);
    root->right->right = new TreeNode(6);
    assert(s.isValidBST(root) == false);

    root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(6);
    root->right->left = new TreeNode(3);
    root->right->right = new TreeNode(7);
    assert(s.isValidBST(root) == false);

    return 0;
}

Comments