Binary Search Tree

Algorithms
tree
Catalogue
  1. 1. Validation
    1. 1.1. 98. Validate Binary Search Tree
      1. 1.1.1. Sol1. Primitive Idea
      2. 1.1.2. Sol2. Range
      3. 1.1.3. Sol3. Inorder Traversal
  2. 2. Insert & Delete
    1. 2.1. 701. Insert into a Binary Search Tree
    2. 2.2. 450. Delete Node in a BST
  3. 3. Search
    1. 3.1. 700. Search in a Binary Search Tree
    2. 3.2. LintCode 11. Search Range in Binary Search Tree
    3. 3.3. 938. Range Sum of BST
    4. 3.4. 270. Closest Binary Search Tree Value
    5. 3.5. 272. Closest Binary Search Tree Value II
      1. 3.5.1. Sol1. Inorder Traversal
      2. 3.5.2. Sol2. Successor & Predecessor
    6. 3.6. 530. Minimum Absolute Difference in BST
  4. 4. Build a BST
    1. 4.1. 108. Convert Sorted Array to Binary Search Tree
    2. 4.2. 109. Convert Sorted List to Binary Search Tree
  5. 5. Iterator
    1. 5.1. 173. Binary Search Tree Iterator

Binary Search Tree: for every single node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.

  • any(left_substree) < root.val < any(right_subtree)
  • for every sigle node in the tree
  • for normal BST, we do not consider equal!

Validation

You have to know the definition of BST and how to use recursion to do validation!

98. Validate Binary Search Tree

Sol1. Primitive Idea

Time : O(n * h)
for each node,

  • check all its left-subtree, to determine whether they all smaller,
  • check all its right-subtree, to determine wheter they are all larger.

Sol2. Range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(n), Space : O(h)
class Solution(object):
    def isValidBST(self, root):
        return self.helper(root, -float('inf'), float('inf'))

    def helper(self, root, tmin, tmax):
        if not root:
            return True

        # BST 是不能有等于的！
        if root.val >= tmax or root.val <= tmin:
            return False

        return (self.helper(root.left, tmin, root.val)
            and self.helper(root.right, root.val, tmax))

Sol3. Inorder Traversal

BST Inorder traversal you will get an strictly increasing array!**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Time : O(n), Space : O(n)
class Solution(object):
    def isValidBST(self, root):
        res = []
        self.dfs(root, res)

        for i in xrange(len(res)-1):
            if res[i+1] <= res[i]:
                return False
        return True

    def dfs(self, root, res):
        if not root:
            return

        self.dfs(root.left, res)
        res.append(root.val)
        self.dfs(root.right, res)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Time : O(n), Space : O(h)
class Solution(object):
    def isValidBST(self, root):
        self.prev = None
        self.is_bst = True
        self.dfs(root)
        return self.is_bst

    def dfs(self, root):
        if not root:
            return

        self.dfs(root.left)
        if self.prev is not None and root.val <= self.prev:
            self.is_bst = False
            return
        self.prev = root.val
        self.dfs(root.right)

Insert & Delete

701. Insert into a Binary Search Tree

1
2
3
4
5
6
7
8
9
10
# Time : O(height), Space : O(height)
class Solution(object):
    def insertIntoBST(self, root, val):
        if not root:
            return TreeNode(val)
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        else:
            root.left = self.insertIntoBST(root.left, val)
        return root

450. Delete Node in a BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def deleteNode(self, root, key):
        if not root:
            return None

        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left and not root.right:
                return None
            elif not root.left or not root.right:
                return root.left if root.left else root.right
            else:
                # Trick Point : swap the largest number in its left subree with current node
                # then we recursion delete the new val in its subtree
                cur = root.right
                while cur.left:
                    cur = cur.left
                root.val = cur.val
                root.right = self.deleteNode(root.right, cur.val)
        return root

700. Search in a Binary Search Tree

Totally based on the definition of BST!

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
# Recursion
Time : O(h), Space : O(h)
class Solution(object):
    def searchBST(self, root, val):
        if not root: return None

        if root.val == val: return root
        elif root.val > val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

# Iteration
Time : O(h), Space : O(1)
class Solution(object):
    def searchBST(self, root, val):
        cur = root
        while cur:
            if cur.val == val:
                return cur
            elif cur.val < val:
                cur = cur.right
            else:
                cur = cur.left
        return None

LintCode 11. Search Range in Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def searchRange(self, root, k1, k2):
       self.res = []
       self.dfs(root, k1, k2)
       return self.res

    def dfs(self, root, k1, k2):
        if not root:
            return

        if k1 < root.val:
            self.dfs(root.left, k1, k2)

        if  k1 <= root.val <= k2:
            self.res.append(root.val)

        if root.val < k2:
            self.dfs(root.right, k1, k2)

938. Range Sum of BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def rangeSumBST(self, root, L, R):
        if not root:
            return 0

        if L > root.val:
            return self.rangeSumBST(root.right, L, R)

        if R < root.val:
            return self.rangeSumBST(root.left, L, R)

        left = self.rangeSumBST(root.left, L, R)
        right = self.rangeSumBST(root.right, L, R)
        return left + right + root.val

270. Closest Binary Search Tree Value

  • Binary Search Tree actually seperate ordered list to three part, less than root.val, root.val, more than root.val instead of two part!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def closestValue(self, root, target):
        cur = root
        res = cur.val
        while cur:
            if abs(cur.val - target) < abs(res - target):
                res = cur.val

            if cur.val == target:
                return cur.val
            elif cur.val < target:
                cur = cur.right
            else:
                cur = cur.left
        return res

272. Closest Binary Search Tree Value II

Sol1. Inorder Traversal

  • Time : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def closestKValues(self, root, target, k):
        res = []
        self.dfs(root, res)
        # Two Pointer Shrink
        left, right = 0, len(res)-1
        while right - left + 1 > k:
            if abs(res[left] - target) < abs(res[right] - target):
                right -= 1
            else:
                left += 1
        return res[left:right+1]

    def dfs(self, root, res):
        if not root:
            return
        self.dfs(root.left, res)
        res.append(root.val)
        self.dfs(root.right, res)
  • follow up : Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
  • What if we have parent node?

Sol2. Successor & Predecessor

  • Key point : How to find the Successor and Predecessor in BST
  • Q : for every node in BST,
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
class Solution(object):
    def getPredecessor(self, pre):
        cur = pre.pop()
        cur = cur.left
        while cur:
            pre.append(cur)
            cur = cur.right

    def getSuccessor(self, suc):
        cur = suc.pop()
        cur = cur.right
        while cur:
            suc.append(cur)
            cur = cur.left

    def closestKValues(self, root, target, k):
        pre, suc = [], []

        # Init pre & suc
        cur = root
        while cur:
            if cur.val <= target:
                pre.append(cur)
                cur = cur.right
            else:
                suc.append(cur)
                cur = cur.left


        res = []
        for _ in xrange(k):
            if len(suc) == 0 or (len(pre) > 0 and abs(pre[-1].val - target) < abs(suc[-1].val - target)):
                res.append(pre[-1].val)
                self.getPredecessor(pre)
            else:
                res.append(suc[-1].val)
                self.getSuccessor(suc)
        return res

530. Minimum Absolute Difference in BST

  • Inorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def getMinimumDifference(self, root):
        self.res = float('inf')
        self.dfs(root, [-float('inf')])
        return self.res

    def dfs(self, root, prev):
        if not root:
            return

        self.dfs(root.left, prev)
        if prev:
            self.res = min(self.res, root.val - prev[-1])
            prev[-1] = root.val
        self.dfs(root.right, prev)

Build a BST

108. Convert Sorted Array to Binary Search Tree

1
2
3
4
5
6
7
8
9
class Solution(object):
    def sortedArrayToBST(self, nums):
        if not nums:
            return None
        mid = len(nums) / 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

109. Convert Sorted List to Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def sortedListToBST(self, head):
        if not head:
            return None

        if not head.next:
            return TreeNode(head.val)

        # Find mid
        slow, fast = head, head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        root = TreeNode(slow.next.val)
        nxt = slow.next.next
        slow.next = None
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(nxt)
        return root

Iterator

173. Binary Search Tree Iterator

If we use Two Stack to solve PostOrder Traversal, Problem “Inorder Traversal” is more complexity than other two traversal! Whether it is or not a binary search tree, the solutions are the same!

  • 1 push element to the stack until its left node is none
  • 2 pop a node from the stack, traverse its right subtree
  • Inorder Traversal Seperated two parts!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class BSTIterator(object):
    def __init__(self, root):
        cur = root
        self.stack = []
        while cur:
            self.stack.append(cur)
            cur = cur.left

    def hasNext(self):
        return len(self.stack) > 0

    def next(self):
        node = self.stack.pop()
        cur = node.right
        while cur:
            self.stack.append(cur)
            cur = cur.left
        return node.val
Share