Binary search trees
Binary search finds values quickly in a sorted array, as long as the array does not change. In this lesson the collection changes while we use it: new values arrive between lookups. We keep a set of distinct numbers and want three operations:
- add a number to the set;
- say whether a number is in the set;
- find the smallest number in the set that is at least .
Suppose the set holds 1, 3, 6, 8, 10 and 14. Then 6 is in the set and 7 is not, and the smallest number that is at least 7 is 8. A booking calendar uses the third operation whenever it looks up the next booking that starts at or after a given time.
A sorted array does the second and the third operation by binary search, in about comparisons for numbers. Adding is the slow one. The new number has to go in its sorted place, and every larger number moves one cell to the right to make room for it:
In the worst case the numbers arrive in decreasing order. Each one then goes to the front and moves all the numbers that are already there, so numbers take moves. For 200,000 numbers that is
A computer copies a block of neighbouring numbers much faster than it runs the separate steps of a program: on our machine bisect.insort made these moves in about 5 seconds. That is still too slow for a typical time limit, and the moves grow with the square of : a million numbers make 25 times as many.
A hash set adds a number and looks one up in expected time. It keeps its numbers in no particular order, though, so the only way to find the smallest one that is at least is to read them all.
A third structure, the binary search tree, does all three in time that depends on its height :
| Stored as | Add | Is in the set? | Smallest value at least |
|---|---|---|---|
| Sorted array | |||
| Hash set | expected | expected | |
| Binary search tree of height |
A search tree keeps the numbers in the nodes of a binary tree, placed so that each of the three operations only has to walk down one path from the root. So an operation visits at most nodes, where is the height of the tree, the number of nodes on its longest path from the root down. For 200,000 numbers the height can be as small as 18, and the last part of the lesson shows when it is.
Definition
A binary search tree (BST) is a binary tree in which, at every node, every value in the left subtree is smaller than the node's value and every value in the right subtree is larger.
We call this condition the ordering rule.
A search tree of six numbers
Here is a binary search tree that holds our six numbers.
The left subtree of the root holds 3, 1 and 6, which are all smaller than 8, and the right subtree holds 10 and 14, which are larger. The same is true one level down, at 3 and at 10.
The rule is about everything below a node. The 6 is the right child of 3, and it is also in the left subtree of 8, so it has to be larger than 3 and smaller than 8.
Search along one path
To find out whether a value is in the tree, we start at the root and compare the value with the node we are at.
- If the two are equal, we have found the value.
- If the value is smaller than the node, it can only be in the left subtree, because everything in the right subtree is larger than the node. We move to the left child.
- If the value is larger, we move to the right child for the same reason.
We repeat this at every node we reach, and if the child we want to move to is missing, the value is not in the tree.
Take the search for 6 in our tree. 6 is smaller than 8, so we go left to 3. 6 is larger than 3, so we go right, and the node there is 6. The search for 7 goes the same way and then tries to go right from 6, where there is no child:
- the search for 7
Both searches made three comparisons and never looked at 1, 10 or 14. Each comparison rules out a whole subtree, the way one comparison in binary search rules out a whole side of the array.
You get the root of a BST and a value val. Find the node whose value is val and return the subtree rooted at that node. If no node holds val, return null.
Constraints
- The tree has between 1 and 5,000 nodes
Sample 1 · Input
root = [4,2,7,1,3], val = 2
Output
[2,1,3]
Sample 2 · Input
root = [4,2,7,1,3], val = 5
Output
[]
The samples write the tree as a list, level by level, the way LeetCode writes trees: the root is 4, its children are 2 and 7, and 1 and 3 are the children of 2. The function returns the node it found, which LeetCode prints together with everything below it.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def search_bst(root, val):
node = root
while node is not None and node.val != val:
if val < node.val:
node = node.left # val can only be in the left subtree
else:
node = node.right # val can only be in the right subtree
return node
# the sample tree [4,2,7,1,3]
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
found = search_bst(root, 2)
print(found.val, found.left.val, found.right.val) # 2 1 3
print(search_bst(root, 5)) # NoneThe loop ends when node is None, because the search ran off the tree, or when node holds the value, and in both cases node is the result.
A search moves down one level with each comparison, so in a tree of height it makes at most comparisons, and it stores nothing except the node it is at. That is time and extra memory.
The smallest value that is at least x
The third operation from the first part asks for the smallest value in the tree that is at least . If is in the tree, the answer is itself. If it is not, the search for fails, and the answer is the next value above . For the answer is 8, and the failed search for 7 still tells us where to find it.
The search for 7 visited 8, 3 and 6. At 8 it turned left, because 8 is larger than 7. That makes 8 a possible answer, and it rules out the right subtree of 8: its values are all larger than 8, so none of them can be the answer. At 3 and at 6 it turned right, because these values are smaller than 7, and that rules out both of them and everything in their left subtrees. Every node of the tree is either on the walk or in a subtree the walk ruled out, so the answer is one of the nodes where the walk turned left.
We keep the last such node in a variable best. A later left turn replaces it, because the new node is in the left subtree of the old one and therefore smaller. A node equal to is treated like a larger one: it becomes best and the walk goes on to the left, where every value is smaller than , so best does not change again.
| At node | Comparison | Move | best afterwards |
|---|---|---|---|
| 8 | left | 8 | |
| 3 | right | 8 | |
| 6 | right | 8 | |
| a missing child | stop | 8, the answer |
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def smallest_at_least(root, x):
best = None
node = root
while node is not None:
if node.val >= x:
best = node # a possible answer; a smaller one can only be on the left
node = node.left
else:
node = node.right # this node and its left subtree are all below x
return best
# our tree [8,3,10,1,6,null,14]
root = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10, None, TreeNode(14)))
for x in [7, 11, 6, 15]:
best = smallest_at_least(root, x)
print(best.val if best else None) # 8, 14, 6, NoneFor 15 the walk turns right at 8, 10 and 14, and best is still empty at the end, because no value in the tree is that large.
The largest value that is at most is found by the mirror image of this walk: a node that is at most becomes best and the walk turns right. The smallest value of the whole tree needs no comparisons: we follow left children from the root until there is none, which leads to 1 in our tree, and right children lead to the largest value, 14. Each of these walks takes time.
Read the values in sorted order
An inorder walk visits the left subtree of a node, then the node, then its right subtree. On our tree it reads the values 1, 3, 6, 8, 10, 14, in sorted order. The inorder list of a search tree is always sorted, and the ordering rule is the reason.
Look at the root first. Inorder lists the whole left subtree, then 8, then the whole right subtree. Every value on the left is smaller than 8 and every value on the right is larger, so 8 is in its sorted place:
Each group is the inorder list of a smaller search tree, so the same argument works inside it. The left group comes from the subtree under 3: 1, then 3, then 6, with 3 in its sorted place. Repeating the argument down to single nodes puts every value in its sorted place, so one traversal lists the values of a search tree in sorted order, in time.
The k-th smallest value
You get the root of a BST with nodes and a number . Return the -th smallest value in the tree, counting from 1.
Constraints
Sample 1 · Input
root = [3,1,4,null,2], k = 1
Output
1
Sample 2 · Input
root = [5,3,6,2,4,null,null,1], k = 3
Output
3
The -th smallest value is the -th entry of the inorder list. The tree of the second sample holds the values 1 to 6, so its inorder list is
and its third entry is 3. So one solution collects the list with an inorder traversal and returns its -th entry, which is at index because the list is indexed from 0:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
sys.setrecursionlimit(20000) # a chain of 10,000 nodes nests 10,000 calls
def kth_smallest(root, k):
values = []
def visit(node):
if node is None:
return
visit(node.left)
values.append(node.val)
visit(node.right)
visit(root)
return values[k - 1]
# the samples [3,1,4,null,2] and [5,3,6,2,4,null,null,1]
first = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))
second = TreeNode(5, TreeNode(3, TreeNode(2, TreeNode(1)), TreeNode(4)), TreeNode(6))
print(kth_smallest(first, 1)) # 1
print(kth_smallest(second, 3)) # 3The traversal reads all nodes, which is fast enough for the nodes allowed here. It does more work than it has to when is small, and the first of the two Deeper reads below stops after values.
Deeper read: stop after k values with a stack
A recursive traversal is awkward to stop in the middle, because the answer has to be passed back through every open call. A loop that keeps its own stack of nodes in place of the recursive calls can return as soon as it has listed values. It starts with the root as the current node and repeats three steps:
- From the current node, move left as far as possible, and push every node on the way onto the stack.
- Pop a node. Everything pushed after it was in its left subtree and has been listed, so its value is the next one in sorted order.
- Make the right child of that node the current node and go back to step 1. If there is no right child, step 1 pushes nothing and step 2 pops again.
In the second sample, 5 has the children 3 and 6, 3 has the children 2 and 4, and 2 has the left child 1. With the loop pushes 5, 3, 2 and 1, pops 1, pops 2, pops 3 and returns 3, before it reaches 4 or 6.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def kth_smallest(root, k):
stack, node = [], root
while True:
while node is not None: # step 1: as far left as possible
stack.append(node)
node = node.left
node = stack.pop() # step 2: the next value in sorted order
k -= 1
if k == 0:
return node.val
node = node.right # step 3
# the samples [3,1,4,null,2] and [5,3,6,2,4,null,null,1]
first = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))
second = TreeNode(5, TreeNode(3, TreeNode(2, TreeNode(1)), TreeNode(4)), TreeNode(6))
print(kth_smallest(first, 1)) # 1
print(kth_smallest(second, 3)) # 3The loop pops nodes, and the nodes it pushed but did not pop are still on the stack when it returns. Each node on the stack is in the left subtree of the node below it, so they all lie on one path down from the root, and there are at most of them. So the loop pushes at most nodes and takes time and memory. The constraints say that is at most . Without that, the stack could run empty, and the loop would have to check for it before it pops.
Deeper read: the k-th smallest value in a tree that keeps changing
LeetCode's follow-up asks what to do when values are inserted and deleted between many such questions. The answer is to store in each node the number of nodes in its subtree.
At a node whose left child stores the count (0 when there is no left child), the node itself is the -th smallest value of its subtree. If we go left. If the node is the answer. Otherwise the answer is on the right, and the values we leave behind are all smaller than it, so we subtract from and go right. That is one path down, so it takes time.
Insertion and deletion, the subject of the next two parts, each change the tree along one path down from the root, and they keep the counts right by adding or subtracting 1 at every node on that path. A search tree with these counts is called an order statistic tree.
Insert where the search ends
A new value goes into the tree as a leaf, and a search tells us where. We search for the value. If the search finds it, the set already has it and nothing changes. Otherwise the search ends at a missing child, and we put a new node in that place. To add 7 to our tree we go left at 8, right at 3 and right at 6. The 6 has no right child, so 7 becomes the right child of 6.
You get the root of a BST and a value val that is not in the tree. Insert val so that the tree is still a BST, and return its root. Any valid result is accepted.
Constraints
- The tree has between 0 and nodes
- All values are distinct, and
valis not in the tree
Sample 1 · Input
root = [4,2,7,1,3], val = 5
Output
[4,2,7,1,3,5]
Sample 2 · Input
root = [40,20,60,10,30,50,70], val = 25
Output
[40,20,60,10,30,50,70,null,null,25]
In the first sample the search for 5 goes right at 4 and left at 7, which has no left child, so 5 becomes the left child of 7. Other results are valid too: 5 could become the new root, with 4 on its left and 7 on its right. Adding a leaf is the simplest way, and it moves no other node.
The new node is in a correct place because of the route the search took. Take 7 in our tree again: the search turned left at 8, which is larger than 7, and right at 3 and at 6, which are smaller, and these three are the only nodes that have the new node below them. In the figure, beside each node is the range of values allowed in its place, and the empty place that the search reached has the range from 6 to 8.
The search was a loop. A loop that inserts has to remember one more node, the last one it passed, because the new node is stored in a link of that node, its parent. The listing uses recursion instead and needs no such variable. Each call handles one subtree and returns the root of that subtree after the insertion, and the caller stores what it gets back in the link it followed, left or right:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def insert_into_bst(root, val):
if root is None:
return TreeNode(val) # the empty place where the search ended
if val < root.val:
root.left = insert_into_bst(root.left, val)
else:
root.right = insert_into_bst(root.right, val)
return root
def inorder(node):
return inorder(node.left) + [node.val] + inorder(node.right) if node else []
# the sample tree [4,2,7,1,3]
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
root = insert_into_bst(root, 5)
print(inorder(root)) # [1, 2, 3, 4, 5, 7]
print(root.right.left.val) # 5, the new left child of 7
root = None # build our tree from an empty one
for value in [8, 3, 10, 1, 6, 14]:
root = insert_into_bst(root, value)
print(inorder(root)) # [1, 3, 6, 8, 10, 14]A call that is given an empty subtree returns the new node. Every other call returns the node it was given, so storing its result changes nothing. On an empty tree the first call already returns the new node, which is why code that calls insert_into_bst always stores the result as the root, as the loop at the end of the program does. The listing has no branch for a value that is already in the tree, because the constraints exclude that case.
The program checks the result by printing its inorder list, which has to be sorted and contain the 5. Its last lines build our tree from an empty one by inserting the values in the order 8, 3, 10, 1, 6, 14.
Delete a value
An insertion only adds a leaf. A deletion can remove a node from the middle of the tree, and then the nodes below it need a new place.
You get the root of a BST and a key. Delete the node whose value is the key, if there is one, so that the tree is still a BST, and return its root. Any valid result is accepted.
Constraints
- The tree has between 0 and nodes
- All values are distinct
Sample 1 · Input
root = [5,3,6,2,4,null,7], key = 3
Output
[5,4,6,2,null,null,7]
Sample 2 · Input
root = [5,3,6,2,4,null,7], key = 0
Output
[5,3,6,2,4,null,7]
Sample 3 · Input
root = [], key = 0
Output
[]
We first search for the node. What happens next depends on how many children it has. The examples use the tree of the first sample, in which 5 has the children 3 and 6, 3 has the children 2 and 4, and 6 has the right child 7.
- If the node has no children, we remove it. Deleting 7 leaves 6 without children.
- If the node has one child, the child takes its place and brings everything below it along. Deleting 6 makes 7 the right child of 5, and the ordering rule still holds, because 7 was in the right subtree of 5 before.
- If the node has two children, it cannot simply be cut out, because only one link points to it and there are two subtrees to attach. So the node stays where it is and receives a new value, the smallest value in its right subtree. We then delete the node that this value came from, which is easier to remove.
The new value has to be larger than everything in the left subtree and smaller than everything that stays in the right one. Two values in the tree qualify, the ones just below and just above the deleted value in sorted order. We use the one above, which is called the inorder successor of the deleted value. It qualifies for two reasons. It comes from the right subtree, so it is larger than everything in the left subtree, and it is the smallest value of the right subtree, so everything that remains there is larger than it.
We find the successor by moving to the right child and then following left children until there is none. The node we reach has no left child, so removing it is the first or the second case.
In the first sample the node 3 has two children. Its right subtree is the single node 4, so its successor is 4. We write 4 into the node and remove the old 4, which is a leaf:
[5,4,6,2,null,null,7].class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def delete_node(root, key):
if root is None:
return None # the key is not in the tree
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
elif root.left is None: # no children, or only a right child
return root.right
elif root.right is None: # only a left child
return root.left
else: # two children
successor = root.right
while successor.left is not None:
successor = successor.left
root.val = successor.val
root.right = delete_node(root.right, successor.val)
return root
def inorder(node):
return inorder(node.left) + [node.val] + inorder(node.right) if node else []
# the sample tree [5,3,6,2,4,null,7]
root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(6, None, TreeNode(7)))
root = delete_node(root, 3)
print(inorder(root)) # [2, 4, 5, 6, 7]
print(root.left.val) # 4, in the place of 3
root = delete_node(root, 0) # 0 is not in the tree
print(inorder(root)) # [2, 4, 5, 6, 7]A node with no children takes the branch for a missing left child and returns its right child, which is missing too, so the first case needs no branch of its own. In the last branch the function calls itself on the right subtree to remove the node whose value it copied.
A deletion walks down to the node and on to its successor, and the call that removes the successor walks that last stretch a second time. Each of these walks is at most one path down the tree, so a deletion takes time.
A tree to try the operations on
The widget starts from our tree. Search for 7 and then insert it: both walk through 8, 3 and 6. Delete 6, which now has one child, and 7 takes its place. Insert 9, which becomes the left child of 10, and delete 8. It has two children, and its successor is 9, found by going right to 10 and then left. The switch Show allowed ranges writes the range under each node.
The two Reinsert buttons rebuild the tree from the same values in another order, which changes its height. We come back to them in the last part.
Validate a search tree
The operations of the earlier parts are correct only on a tree that follows the ordering rule. The next problem checks whether a given tree does.
You get the root of a binary tree. Return whether it is a valid BST. Equal values are not allowed: a left subtree holds only smaller values and a right subtree only larger ones.
Constraints
- The tree has between 1 and nodes
Sample 1 · Input
root = [2,1,3]
Output
true
Sample 2 · Input
root = [5,1,4,null,null,3,6]
Output
false
In the second sample the root is 5 and its right child is 4, which is smaller, so the answer is false. That suggests a simple check: compare every node with its two children. This check is not enough, and the tree [8,3,10,1,9] shows why.
A tree with every child on the correct side
In this tree every child is on the correct side of its parent: 3 is smaller than 8 and 10 is larger, 1 is smaller than 3 and 9 is larger. But 9 is in the left subtree of 8, and it is larger than 8.
- the search for 9
- outside its allowed range
A search for 9 turns right at 8, finds no left child at 10 and reports that 9 is missing, although it is stored. The rule is about whole subtrees, so comparing a node with its parent is not enough. Each node has to be checked against every node above it.
Pass a range down to every node
A correct check gives every node a range of allowed values, like the ranges in the insertion figure. Each node tests its own value against the range it receives from its parent. The root receives the range without limits. A left child receives its parent's range with the upper limit lowered to the parent's value, and a right child receives it with the lower limit raised. The drawing of [8,3,10,1,9] above has these ranges under its nodes. The 9 is reached by going left at 8 and right at 3, so it receives the range from 3 to 8, and 9 is outside that range.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def valid(node, low, high): # every value under node must lie strictly between low and high
if node is None:
return True
if not low < node.val < high:
return False
return valid(node.left, low, node.val) and valid(node.right, node.val, high)
def is_valid_bst(root):
return valid(root, float('-inf'), float('inf'))
# the samples [2,1,3] and [5,1,4,null,null,3,6], then [8,3,10,1,9]
first = TreeNode(2, TreeNode(1), TreeNode(3))
second = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
third = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(9)), TreeNode(10))
print(is_valid_bst(first), is_valid_bst(second), is_valid_bst(third)) # True False FalseThe test is strict, so a value equal to a limit fails it. The limits start at float('-inf') and float('inf'), which no value in a node can equal.
Every node is tested once, so the check takes time. The sorted order gives a second way to check. The inorder list puts everything in the left subtree of a node before the node and everything in its right subtree after it, so a tree is a search tree exactly when its inorder list is strictly increasing. For [8,3,10,1,9] the list steps down from 9 to 8:
Height and the order of insertion
Search, insertion, deletion and the smallest value at least each walk down one path from the root, so their cost grows with the height of the tree. The height depends on the order in which the values were inserted. Insert 4, 2, 6, 1, 3, 5, 7 into an empty tree, and 4 becomes the root with two full levels below it. Insert the same seven values in sorted order, and each one becomes the right child of the one before:
A tree of height has at most nodes, because a level holds at most twice as many nodes as the level above it. So 200,000 values need at least 18 levels, since 17 levels hold only . In a chain they fill 200,000 levels.
The two Reinsert buttons of the operations widget show both extremes. For our six values, sorted order gives a chain of height 6, and inserting the middle value first gives a tree of height 3.
The seven values 1 to 7 can be inserted in 5,040 orders. Only 80 of them build the full tree of height 3, and only 64 build a chain of height 7, the sorted order among them. Most of the rest, 4,288, have height 4 or 5.
So a random order rarely gives either extreme, and with many values its tree is much closer to the best height than to a chain. On average a search in it passes through fewer than nodes, where is the natural logarithm. For 200,000 values that bound is about 24, and our five runs averaged about 22, against at most 18 in the best tree and about 100,000 in a chain.
| Order of insertion | Height | Comparisons in one search |
|---|---|---|
| the middle value first, then the middle of each half | 18 | at most 18 |
| random | 41 to 45 in five runs of ours | up to about 45 |
| sorted | 200,000 | up to 200,000 |
In a chain a search passes the values one at a time, like reading a sorted array from the front. Inserting 200,000 values in sorted order walks past nodes, steps in all, as many as the moves of the sorted array.
Each step follows a link to another node, which is much slower than copying neighbouring numbers. At the 18 million links a second Python followed on our machine, these inserts would take about 20 minutes. A chain also breaks the recursive insert: the calls nest one level deeper for each node on the path, and at about the 1,000th value they exceed the default limit and stop with a RecursionError.
Input can easily arrive sorted, since timestamps and record numbers come in increasing order. A balanced search tree prevents the chain. After each insertion and deletion it rearranges a few nodes near the path it walked, which keeps the height at whatever the order of the values. AVL trees and red-black trees are the best-known kinds. A red-black tree of values has height at most , at most 35 for 200,000 values. In a balanced tree, search, insertion, deletion and the smallest value at least each take time. This lesson does not write one, but some standard libraries ship one, C++'s set among them.
Sorted sets in the standard library
Python's standard library has no balanced search tree. The closest tool is a sorted list with the bisect module. bisect_left(a, x) finds the index of the smallest value that is at least x by binary search, and insort(a, x) inserts x at its sorted place. The search takes time, but the insertion moves up to values, as in the first part.
Here are the operations of this lesson as library calls on our six numbers:
a = sorted([8, 3, 10, 1, 6, 14]) # [1, 3, 6, 8, 10, 14]
i = bisect_left(a, 7) # the index of the smallest value that is at least 7
print(a[i]) # 8
print(i < len(a) and a[i] == 7) # False: 7 is not in the list
insort(a, 7) # [1, 3, 6, 7, 8, 10, 14]
print(a[bisect_left(a, 7)]) # 7
a.remove(8)
print(a) # [1, 3, 6, 7, 10, 14]
print(bisect_left(a, 15) == len(a)) # True: no value is at least 15On LeetCode the package sortedcontainers is installed as well. Its SortedList has the operations of a balanced tree, add, remove and bisect_left, each in about time. Not every judge installs it, so check the judge's list of packages first; without it, use a sorted list with bisect.
Common mistakes
Starting the validation range at the smallest and largest 32-bit values.
- Where it breaks
- The single node
[2147483647]is a valid tree. With an upper limit of its value is not strictly below the limit, and the tree is reported as invalid. - The fix
- Start with limits that lie outside the range of the values: the two infinities in Python,
long longlimits in C++.
Copying the successor into a node and leaving the node it came from in the tree.
- Where it breaks
- Deleting 3 from
[5,3,6,2,4,null,7]this way gives the inorder list 2, 4, 4, 5, 6, 7, with 4 stored twice. - The fix
- After the copy, delete the successor from the right subtree.
Recall The lowest common ancestor of two nodes is the deepest node that has both of them in its subtree. In an ordinary binary tree it is found by searching both subtrees of a node. How can a search tree find it for two values $p$ and $q$ along one path?
Walk down from the root. While both values are smaller than the node, both are in its left subtree, so move left, and while both are larger, move right. The first node where neither holds is the answer: there the two values go to different sides, or one of them is the node itself. In our tree, 1 and 6 are both smaller than 8, and 3 lies between them, so their lowest common ancestor is 3. The walk takes time. Lowest Common Ancestor of a Binary Search Tree, in this lesson's problem list, asks for it.
Further reading
- USACO Guide, GoldMore Operations on Sorted Sets(opens in a new tab)
lower_bound,upper_bound, iterators and multisets on C++set,sortedcontainersfor Python, and a graded list of problems solved with a sorted set. - Pat MorinOpen Data Structures, Chapter 6: Binary Trees(opens in a new tab)
Section 6.2 covers searching, addition and removal in a binary search tree, with a figure for each, and its search also finds the smallest value at least . Chapter 7 goes on to the insertion orders behind each shape of tree and the length of a search in a tree built in random order, and Chapter 9 bounds the height of a red-black tree. Parts of this page adapt the text of these chapters, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.
- Antti Laaksonen, free PDFCompetitive Programmer’s Handbook, sections 4.2 to 4.4(opens in a new tab)
Pages 37 to 41:
set,mapand their iterators in C++, with the code for finding the value nearest to . - MIT 6.006, Spring 2020Lecture 7: Binary Trees, Part 2: AVL(opens in a new tab)
How rotations keep an AVL tree at height after every insertion and deletion.
- Python Sorted Containers documentationSorted List(opens in a new tab)
Every method of
SortedListwith its running time, for Python readers who use it on LeetCode. - OI Wiki, in Chinese二叉搜索树 & 平衡树(opens in a new tab)
Every operation in this lesson plus the k-th smallest value with subtree sizes, followed by what balance means and how the balanced variants restore it.