Teaching Kids Programming – Algorithms to Find the Inorder Successor of a Binary Search Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary search tree root containing unique values, and an integer t, return the value of the inorder successor of t. That is, return the smallest value greater than t in the tree. Note: you can assume that the inorder successor exists.

Bonus: solve it in O(h) space where h is the height of the tree.

Constraints
n ≤ 100,000 where n is the number of nodes in root

Inorder Successor of a Binary Tree by Converting to List

We can perform the inorder traversal on the binary search tree which will give us a sorted list, and then we just have to search in the target (this bit could be done via Binary Search). Once target is found, we simply return the next one aka successor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderSuccessorBST(self, root, t):
        data = []
        def dfs(root):
            nonlocal data
            if root is None:
                return
            dfs(root.left)
            data.append(root.val)
            dfs(root.right)
        dfs(root)
        i = data.index(t)  # could be done via Binary Search
        if i + 1 < len(data):
            return data[i + 1]

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderSuccessorBST(self, root, t):
        data = []
        def dfs(root):
            nonlocal data
            if root is None:
                return
            dfs(root.left)
            data.append(root.val)
            dfs(root.right)
        dfs(root)
        i = data.index(t)  # could be done via Binary Search
        if i + 1 < len(data):
            return data[i + 1]

The time and space complexity is O(N) where N is the number of the nodes in the binary tree.

Finding Inorder Successor of a Binary Search Tree

Given the binary tree is a BST, we can traverse the tree and look for target in O(H) time where H is the height of the tree. And in a balanced BST, H is roughly LogN where N is the number of the nodes in the BST.

When the target is smaller than the root/current node, we navigate to the left and also update the candidate answer with the value of the current node which is larger than the target. Otherwise, we go to the right when the target node is larger than the root/current node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderSuccessorBST(self, root, t):
        ans = None
        while root:
            if t < root.val:
                ans = root.val
                root = root.left                
            else:
                root = root.right
        return ans

#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderSuccessorBST(self, root, t):
        ans = None
        while root:
            if t < root.val:
                ans = root.val
                root = root.left                
            else:
                root = root.right
        return ans

The time complexity is O(H) or O(LogN) and the space complexity is O(1) constant.

See also: Compute the Inorder Successor of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —