Compute the Inorder Successor of a Binary Tree

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.

Perform an Inorder Traversal and Search for Successor

We can perform a inorder traversal of the binary tree and put results in an array. Then we can search for the target and return its sucessor. This takes O(N) time and O(N) space.

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

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root, t):
        ans = []
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)
        dfs(root)
        return ans[ans.index(t) + 1]

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root, t):
        ans = []
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)
        dfs(root)
        return ans[ans.index(t) + 1]

Inorder Successor of a Binary Tree

Starting from the root, if the target value is smaller than the current node, we update the answer (inorder successor), and navigate to the left tree. Otherwise, we navigate to the right tree.

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

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

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

Time complexity is O(H) where H is the height of the tree. We can also represent the complexity in O(LogN) since in a balanced binary search tree, H = LogN. The space complexity is O(1) constant.

See also: Finding the Predecessor and Successor Node of a Binary Search Tree

–EOF (The Ultimate Computing & Technology Blog) —