Traversals and validation
A traversal visits every node of a tree once. Done recursively, it comes in three classic orders, named after when the node itself comes compared with its two subtrees:
- pre-order: the node, then its left subtree, then its right subtree;
- in-order: the left subtree, then the node, then the right subtree;
- post-order: the left subtree, then the right subtree, then the node.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder(node, out):
if node is not None:
out.append(node.value)
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
if node is not None:
inorder(node.left, out)
out.append(node.value)
inorder(node.right, out)
def postorder(node, out):
if node is not None:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.value)
# 8
# / \
# 3 12
# / \ \
# 1 6 15
root = Node(8, Node(3, Node(1), Node(6)), Node(12, None, Node(15)))
for visit in [preorder, inorder, postorder]:
out = []
visit(root, out)
print(out)[8, 3, 1, 6, 12, 15]
[1, 3, 6, 8, 12, 15]
[1, 6, 3, 15, 12, 8]The tree is a BST, and its in-order is sorted. That's no accident: at every node, the smaller values of its left subtree all come out before it, and the greater values of its right subtree all come out after it.
Each order has its jobs. Pre-order meets every parent before its children, so it's the order for copying or saving a tree: inserting the values into an empty BST in pre-order builds the same tree again. Post-order finishes both children before their parent, which is what size and height did in the first step: they needed the answers of the subtrees first. In-order gives a BST's values in sorted order.
All three are O(n) time: every node is visited once and appended once, to the one list that every call shares. The tempting one-liner return inorder(node.left) + [node.value] + inorder(node.right) gives the same list, but + copies both lists it joins, so a value is copied again at every level above it: O(n·h) time, which is O(n²) for a chain.
Is it a valid BST?
A tempting check compares each node with its own children only:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def looks_valid(node):
if node is None:
return True
if node.left is not None and node.left.value >= node.value:
return False
if node.right is not None and node.right.value <= node.value:
return False
return looks_valid(node.left) and looks_valid(node.right)
# 8
# /
# 3
# \
# 10
print(looks_valid(Node(8, Node(3, None, Node(10)))))TrueThat's wrong. 10 is greater than its parent 3, but it's in the left subtree of 8, where every value must be smaller than 8: a search for 10 goes right at 8 and never finds it. The rule is about whole subtrees, not just children.
The fix is to pass bounds down the tree: every value must lie strictly between a low and a high, and the root has no bounds (None for both). Going left, the node's value becomes the new high, because everything down there must be smaller than it. Going right, it becomes the new low. Above, 3 gets the bounds None and 8, and 10 gets 3 and 8: 10 isn't below 8, so the tree isn't valid. Each node is still checked once, O(n) time. (Another correct check: the in-order must be strictly increasing.)
Deep trees: a stack of your own
A recursive traversal of a chain of 5,000 nodes stops with a RecursionError. The calls that wait on Python's call stack can just as well wait in a list of your own, which can hold millions of items. Used this way, the list is a stack: the item added last is the first to come out, like plates in a pile. append puts an item on top, O(1) amortized, and pop takes the top one off, O(1). For in-order: go as far left as you can, putting each node on the stack. Then pop the top node, visit it, and go on with its right subtree in the same way:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder_loop(root):
out = []
stack = []
node = root
while stack or node is not None:
while node is not None:
stack.append(node)
node = node.left
node = stack.pop()
out.append(node.value)
node = node.right
return out
chain = None
for value in range(5000, 0, -1):
chain = Node(value, None, chain)
values = inorder_loop(chain)
print(len(values), values[:3], values[-1])5000 [1, 2, 3] 5000chain has 1 at the root, 2 as its right child, 3 below that and so on: a valid BST, 5,000 levels deep. append and pop at the end of a list are O(1), so the loop is O(n) time and O(h) memory, like the recursion, but without its limit.
Two more jobs for a stack
A stack fits whenever the newest open item must be dealt with first. Matching brackets is the classic: in ([]{}) every closing bracket closes the last bracket still open. Go through the text, push each opening bracket, and at each closing bracket pop the top and check that the two are a pair. If the stack is empty at a closing bracket, or the top isn't its partner, the text isn't balanced: )( fails at once. It is balanced when every check passes and the stack ends empty. That's one pass, O(n).
A stack kept in order finds the next greater value to the right of each item, such as how many days you wait for a warmer day. Keep a stack of the days still waiting for their answer. Their temperatures never rise from the bottom of the stack to the top, which is why it's called a monotonic stack. Each new day pops every waiting day that is colder, since it's their answer, and then waits itself:
def days_until_warmer(temps):
answer = [0] * len(temps)
waiting = []
for day, temp in enumerate(temps):
while waiting and temps[waiting[-1]] < temp:
earlier = waiting.pop()
answer[earlier] = day - earlier
waiting.append(day)
return answer
print(days_until_warmer([18, 16, 17, 21, 19, 19, 23, 15]))[3, 1, 1, 3, 2, 1, 0, 0]The 21 on day 3 pops the 17 and then the 18 of day 0, which waited 3 days. The last two days never see a warmer one, so they keep their 0. There's a loop inside a loop, but each day is pushed once and popped at most once, so the function is O(n). Comparing each day with every later one would be O(n²).