Inorder Predecessor in BST
franklinqin0 Tree
# Definition for a Binary Tree Node
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
1
2
3
4
2
3
4
# Solution
Let be the height and be the number of nodes of tree.
# Brute Force
Brute force would be to traverse all nodes and then search for the node before p
, but that's obviously inefficient.
Complexity
time:
space:
# Vanilla Iteration
Return the rightmost node of left subtree, if any; otherwise, return the lowest left father instead.
Complexity
time:
space:
def inorderPredecessor(self, root, p):
if not root:
return None
lowest_left_father = None
# find lowest left father, if any
while root != p:
if root.val < p.val:
lowest_left_father = root
root = root.right
else:
root = root.left
# find rightmost node of left subtree, if any
son = p.left
res = son
while son:
res = son
son = son.right
if not res:
return lowest_left_father
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# DFS
The algorithms of iteration and recursion are similar and both take time:
- if current
node
's value is larger than or equal top
's value, we know our answer must be in the left subtree - if current
node
's value is less thanp
's value, current node is a candidate. Go to its right subtree to see if we can find a larger one - if we reach null, our search is over, just return the candidate
but recursion would require implicit stack space.
# Iteration
def inorderPredecessor(self, root, p):
res = None
node = root
while node:
if node.val >= p.val:
node = node.left
else:
res = node
node = node.right
return res
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# Recursion
class Solution:
pre = None
def inorderPredecessor(self, root, p):
def dfs(root, p):
if not root:
return
if root.val >= p.val:
dfs(root.left, p)
else:
self.pre = root
dfs(root.right, p)
dfs(root, p)
return self.pre
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15