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 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)

[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 230] Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

1
2
3
4
5
6
7
8
       3
     /   \
    1     4
     \
      2

Input: root = [3,1,4,null,2], k = 1
Output: 1

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Solution:

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
# 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 kthSmallest1(self, root: Optional[TreeNode], k: int) -> int:
        # create a stack to store the nodes
        stack = []
        # start at the root of the tree
        current = root

        # loop until we have processed all nodes and found the kth smallest value
        while True:
            # traverse as far left as possible from the current node, adding each node to the stack
            while current is not None:
                stack.append(current)
                current = current.left

            # if the stack is empty, we have processed all nodes and can exit the loop
            # if not stack:
            #    break

            # pop the top node off the stack (which is the next smallest node) and decrement k
            node = stack.pop()
            k -= 1

            # if k is 0, we have found the kth smallest value and can return it
            if k == 0:
                return node.val

            # set the current node to the right child of the node we just processed
            current = node.right

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

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.st = []

        self.traverseLeft(root)

        while True:
            # get next smallest node
            node = self.st.pop()

            # check if this is the kth smallest node
            k -= 1
            if k == 0:
                return node.val

            # traverse right subtree before go back to parent
            node = node.right
            self.traverseLeft(node)