Binary search tree in Python

Posted on Edited on In , Views:

Intro

Binary Search Tree is a binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with values smaller than the node.
  • The right subtree of a node contains only nodes with values greater than the node.
  • The left and right subtree each must also be a binary search tree.

Based on the properties, we can implement a algorithm to check if a binary tree is binary search tree.

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import sys
    
class BST:

    class Node:
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    
    
    # left most node is minimum
    def minVal(node):
        current = node
    
        while current.left != None:
            current = current.left
    
        return current.val
    
    
    # right most node is maximum
    def maxVal(node):
        current = node
    
        while current.right != None:
            current = current.right
    
        return current.val
    
    
    # not efficient since some nodes are traversed multiple times
    def isBst(node):
        if node == None:
            return True
    
        if node.left and node.val < minVal(node.left):
            return False
        if node.right and node.val > maxVal(node.right):
            return False
    
        if (not isBst(node.left)) or (not isBst(node.right)):
            return False
    
        return True
    
    
    def isBstOptimal(node, min, max):
        if node == None:
            return True
    
        if node.val < min or node.val > max:
            return False
    
        return isBstOptimal(node.left, min, node.val) and isBstOptimal(
            node.right, node.val, max
        )
    
    
    def binarySearch(node, target):
        if node == None:
            return False
    
        if node.val == target:
            return True
    
        if node.val > target:
            return binarySearch(node.left, target)
        elif node.val < target:
            return binarySearch(node.right, target)
    
    
    #
    #          6
    #        /   \
    #       4     8
    #      / \   / \
    #     2   5 7   9
    #    / \
    #   1   3
    #
    root = Node(6)
    n1 = Node(4)
    n2 = Node(8)
    root.left = n1
    root.right = n2
    n3 = Node(2)
    n4 = Node(5)
    n1.left = n3
    n1.right = n4
    n5 = Node(7)
    n6 = Node(9)
    n2.left = n5
    n2.right = n6
    n7 = Node(1)
    n8 = Node(3)
    n3.left = n7
    n3.right = n8
    
    print(isBst(root))
    print(isBstOptimal(root, -sys.maxsize, sys.maxsize))
    
    n9 = Node(9)
    n7.left = n9
    
    print(isBst(root))
    print(isBstOptimal(root, -sys.maxsize, sys.maxsize))
    
    print(binarySearch(root, 8))
    print(binarySearch(root, 11))
    print(binarySearch(root, -1))

[Leetcode 173] Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

  • BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
  • boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
  • int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
        3
      /   \ 
     7    15
         /  \
        9   20 
Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

Constraints:

  • The number of nodes in the tree is in the range [1, 10^5].
  • 0 <= Node.val <= 10^6
  • At most 10^5 calls will be made to hasNext, and next.

Follow up:

  • Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?
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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator_bf:

    def __init__(self, root: Optional[TreeNode]):
        self.currIndex = 0
        self.data = []
        self.inOrder(root)

    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.left)
        self.data.append(root.val)
        self.inOrder(root.right)

    def next(self) -> int:
        val = self.data[self.currIndex]
        self.currIndex += 1
        return val

    def hasNext(self) -> bool:
        return self.currIndex <= len(self.data) - 1


class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.st = []
        self.traverse(root) 

    def traverse(self, root):
        while root != None:
            self.st.append(root)
            root = root.left

    def next(self) -> int:
        node = self.st.pop()
        self.traverse(node.right)
        return node.val

    def hasNext(self) -> bool:
        return len(self.st) > 0


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

[Leetcode 108] Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced binary search tree.

Example 1:

1
2
3
4
5
6
7
8
         0
        / \
      -3   9
      /   /
    -10  5
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

1
2
3
4
5
6
    3   1
   /     \
  1       3
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in a strictly increasing order.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructTree(self, nums, low, high):
        if low > high:
            return None

        mid = low + (high - low) // 2
        root = TreeNode(nums[mid])
        root.left = self.constructTree(nums, low, mid - 1)
        root.right = self.constructTree(nums, mid + 1, high)
        return root

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.constructTree(nums, 0, len(nums) - 1)