Binary Search Tree¶
Table of Contents¶
- 235. Lowest Common Ancestor of a Binary Search Tree (Medium)
- 98. Validate Binary Search Tree (Medium)
- 230. Kth Smallest Element in a BST (Medium)
235. Lowest Common Ancestor of a Binary Search Tree¶
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 lowestCommonAncestor(root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
root = build(root)
p = root.left
q = root.right
print(root)
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
print(lowestCommonAncestor(root, p, q))
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
98. Validate Binary Search Tree¶
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;
}
230. Kth Smallest Element in a BST¶
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