Binary Search Tree

Table of Contents

• 98. Validate Binary Search Tree (Medium)
• 230. Kth Smallest Element in a BST (Medium)
• 501. Find Mode in Binary Search Tree (Easy)
• 99. Recover Binary Search Tree (Medium)
• 700. Search in a Binary Search Tree (Easy)
• 530. Minimum Absolute Difference in BST (Easy)
• 783. Minimum Distance Between BST Nodes (Easy)
• 1305. All Elements in Two Binary Search Trees (Medium)
• 938. Range Sum of BST (Easy)
• 897. Increasing Order Search Tree (Easy)
• 2476. Closest Nodes Queries in a Binary Search Tree (Medium)
• 653. Two Sum IV - Input is a BST (Easy)
• 1373. Maximum Sum BST in Binary Tree (Hard)
• 1932. Merge BSTs to Create Single BST (Hard)
• 285. Inorder Successor in BST (Medium) 👑
• 510. Inorder Successor in BST II (Medium) 👑
• 270. Closest Binary Search Tree Value (Easy) 👑
• 272. Closest Binary Search Tree Value II (Hard) 👑
• 255. Verify Preorder Sequence in Binary Search Tree (Medium) 👑
• 1902. Depth of BST Given Insertion Order (Medium) 👑

98. Validate Binary Search Tree

• LeetCode | LeetCode CH (Medium)

• Tags: tree, depth first search, binary search tree, binary tree

98. Validate Binary Search Tree - Python Solution

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


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

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

    dfs(root)

    for i in range(1, len(inorder)):
        if inorder[i] <= inorder[i - 1]:
            return False

    return True


root = [5, 1, 4, None, None, 3, 6]
root = build(root)
print(root)
#   5__
#  /   \
# 1     4
#      / \
#     3   6
print(isValidBST(root))  # False
# [1, 5, 3, 4, 6]

98. Validate Binary Search Tree - C++ Solution

#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;
}

230. Kth Smallest Element in a BST

• LeetCode | LeetCode CH (Medium)

• Tags: tree, depth first search, binary search tree, binary tree

230. Kth Smallest Element in a BST - Python Solution

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


root = build([3, 1, 4, None, 2])
k = 1
print(root)
#   __3
#  /   \
# 1     4
#  \
#   2
print(kthSmallestRecursive(root, k))  # 1
print(kthSmallestIteratve(root, k))  # 1

501. Find Mode in Binary Search Tree

• LeetCode | LeetCode CH (Easy)

• Tags: tree, depth first search, binary search tree, binary tree

501. Find Mode in Binary Search Tree - Python Solution

from typing import List, 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 findMode(root: Optional[TreeNode]) -> List[int]:
    hashmap = dict()

    def dfs(node):
        if not node:
            return None
        dfs(node.left)
        if node.val not in hashmap:
            hashmap[node.val] = 1
        else:
            hashmap[node.val] += 1
        dfs(node.right)

    dfs(root)
    max_counts = max(hashmap.values())
    result = []

    for key, value in hashmap.items():
        if value == max_counts:
            result.append(key)

    return result


root = [1, None, 2, None, None, 2]
root = build(root)
print(root)
# 1__
#    \
#     2
#    /
#   2
print(findMode(root))  # [2]

99. Recover Binary Search Tree

• LeetCode | LeetCode CH (Medium)

• Tags: tree, depth first search, binary search tree, binary tree

700. Search in a Binary Search Tree

• LeetCode | LeetCode CH (Easy)

• Tags: tree, binary search tree, binary tree

Binary Search Tree

1. Binary Tree
2. Left subtree of a node contains only nodes with keys less than the node's key
3. Right subtree of a node contains only nodes with keys greater than the node's key
4. The left and right subtree each must also be a binary search tree
5. There must be no duplicate nodes
6. Inorder traversal of a BST gives a sorted list of keys

graph TD
4((4)) --- 2((2))
4 --- 7((7))
2 --- 1((1))
2 --- 3((3))

700. Search in a Binary Search Tree - Python Solution

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


# 1. Recursive
def searchBSTRecursive(
    root: Optional[TreeNode], val: int
) -> Optional[TreeNode]:
    if not root:
        return None

    if root.val > val:
        return searchBSTRecursive(root.left, val)

    elif root.val < val:
        return searchBSTRecursive(root.right, val)

    else:
        return root


# 2. Iterative
def searchBSTIterative(
    root: Optional[TreeNode], val: int
) -> Optional[TreeNode]:
    while root:
        if root.val > val:
            root = root.left
        elif root.val < val:
            root = root.right
        else:
            return root
    return None


root = [4, 2, 7, 1, 3]
val = 2
root = build(root)
print(root)
#     __4
#    /   \
#   2     7
#  / \
# 1   3
print(searchBSTRecursive(root, val))
#   2
#  / \
# 1   3
print(searchBSTIterative(root, val))
#   2
#  / \
# 1   3

530. Minimum Absolute Difference in BST

• LeetCode | LeetCode CH (Easy)

• Tags: tree, depth first search, breadth first search, binary search tree, binary tree

530. Minimum Absolute Difference in BST - Python Solution

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:

    inorder = []
    result = float("inf")

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

    dfs(root)

    for i in range(1, len(inorder)):
        result = min(result, abs(inorder[i] - inorder[i - 1]))

    return result


root = [4, 2, 6, 1, 3]
root = build(root)
print(root)
#     __4
#    /   \
#   2     6
#  / \
# 1   3
print(getMinimumDifference(root))  # 1

783. Minimum Distance Between BST Nodes

• LeetCode | LeetCode CH (Easy)

• Tags: tree, depth first search, breadth first search, binary search tree, binary tree

1305. All Elements in Two Binary Search Trees

• LeetCode | LeetCode CH (Medium)

• Tags: tree, depth first search, binary search tree, sorting, binary tree

938. Range Sum of BST

• LeetCode | LeetCode CH (Easy)

• Tags: tree, depth first search, binary search tree, binary tree

897. Increasing Order Search Tree

• LeetCode | LeetCode CH (Easy)

• Tags: stack, tree, depth first search, binary search tree, binary tree

2476. Closest Nodes Queries in a Binary Search Tree

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search, tree, depth first search, binary search tree, binary tree

653. Two Sum IV - Input is a BST

• LeetCode | LeetCode CH (Easy)

• Tags: hash table, two pointers, tree, depth first search, breadth first search, binary search tree, binary tree

1373. Maximum Sum BST in Binary Tree

• LeetCode | LeetCode CH (Hard)

• Tags: dynamic programming, tree, depth first search, binary search tree, binary tree

1932. Merge BSTs to Create Single BST

• LeetCode | LeetCode CH (Hard)

• Tags: hash table, binary search, tree, depth first search, binary tree

285. Inorder Successor in BST

• LeetCode | LeetCode CH (Medium)

• Tags: tree, depth first search, binary search tree, binary tree

510. Inorder Successor in BST II

• LeetCode | LeetCode CH (Medium)

• Tags: tree, binary search tree, binary tree

270. Closest Binary Search Tree Value

• LeetCode | LeetCode CH (Easy)

• Tags: binary search, tree, depth first search, binary search tree, binary tree

272. Closest Binary Search Tree Value II

• LeetCode | LeetCode CH (Hard)

• Tags: two pointers, stack, tree, depth first search, binary search tree, heap priority queue, binary tree

255. Verify Preorder Sequence in Binary Search Tree

• LeetCode | LeetCode CH (Medium)

• Tags: array, stack, tree, binary search tree, recursion, monotonic stack, binary tree

1902. Depth of BST Given Insertion Order

• LeetCode | LeetCode CH (Medium)

• Tags: array, tree, binary search tree, binary tree, ordered set

Comments