forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbst_validate_bst.py
More file actions
89 lines (76 loc) · 2.71 KB
/
bst_validate_bst.py
File metadata and controls
89 lines (76 loc) · 2.71 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# ===============================================================================
# Validate Binary Search Tree
"""
To check if the given binary tree is a valid binary search
tree (BST), we need to ensure that:
1. The left subtree of a node contains only nodes with
keys less than the node's key.
2. The right subtree of a node contains only nodes with
keys greater than the node's key.
3. Both the left and right subtrees must also be binary
search trees.
"""
# ===============================================================================
from algorithms.common.tree_node import TreeNode
# Function to validate if a binary tree is a BST
def validate_bst(node):
"""
Validate if a binary tree is a binary search tree (BST).
Input params : Tree Node to be validated
Returns : Tuple (
is_bst: bool,
min_value: int | None,
max_value: int | None
)
"""
# Base case: An empty tree is a valid BST
if not node:
return (True, None, None)
# Validate the left and right subtrees
valid_left, minn_left, maxx_left = validate_bst(node.left)
valid_right, minn_right, maxx_right = validate_bst(node.right)
# If either subtree is not valid, the whole tree is not a valid BST
if not valid_left or not valid_right:
return (
False,
minn_left if minn_left is not None else node.val,
maxx_right if maxx_right is not None else node.val,
)
# Check the current node's value against the max of the left subtree
if maxx_left is not None and maxx_left > node.val:
return (
False,
minn_left if minn_left is not None else node.val,
maxx_right if maxx_right is not None else node.val,
)
# Check the current node's value against the min of the right subtree
if minn_right is not None and minn_right < node.val:
return (
False,
minn_left if minn_left is not None else node.val,
maxx_right if maxx_right is not None else node.val,
)
# If all checks pass, the tree/subtree is a valid BST
return (
True,
minn_left if minn_left is not None else node.val,
maxx_right if maxx_right is not None else node.val,
)
# Example usage
if __name__ == "__main__":
# Constructing a simple binary tree
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.right.left = TreeNode(12)
root.right.right = TreeNode(20)
"""
10
/ \
5 15
/ \
12 20
"""
# Validate if the constructed tree is a BST
is_bst, _, _ = validate_bst(root)
print(f"The tree is a valid BST: {is_bst}")