Binary trees and recursion
You built binary trees in the recursion module: a Node class with a value and two children, left and right, where None means "no child here", and recursive functions that counted the nodes, added up the values and measured the depth of a tree. This module takes trees on to what interviews ask about them. This step asks what those functions cost and where they break, with a short look at the linked list, a chain of nodes with one link each. The next ones add the order of a search tree, other ways to walk a tree, heaps and tries.
Here are the three functions again, with the names interview questions usually give them: size is the recursion module's count_nodes, and height is its depth.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def size(node):
if node is None:
return 0
return 1 + size(node.left) + size(node.right)
def tree_sum(node):
if node is None:
return 0
return node.value + tree_sum(node.left) + tree_sum(node.right)
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
# 4
# / \
# 9 2
# / \
# 7 5
root = Node(4, Node(9), Node(2, Node(7), Node(5)))
print(size(root), tree_sum(root), height(root))5 27 3Read None as the empty tree. Then a tree is either empty or a node with two smaller trees, its subtrees, and that hands you the shape of almost every tree function:
- The base case: the empty tree,
None. Its answer is usually 0,Trueor an empty list. - Ask the same question of the left subtree and of the right subtree.
- Combine the two answers with the node itself.
Trust the recursion. You don't need to follow every call to know that size is right: if it gives the right answers for the two subtrees, then 1 plus those answers is right for the whole tree. And the calls do end, because each one goes a level down, and the levels run out at None.
Here the height is the number of nodes on the longest path from the root down to a leaf: 3, for the path 4, 2, 7. (Some books count the links between the nodes instead, which gives one less. Interview questions often call this height the "maximum depth".)
A leaf is not enough of a base case
The recursion stops at the leaves, so it's tempting to make the leaf the base case:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node):
if node.left is None and node.right is None:
return 1
return 1 + max(height(node.left), height(node.right))
print(height(Node(4, Node(9), Node(2, Node(7), Node(5)))))
print(height(Node(4, Node(9, Node(1)))))3Traceback (most recent call last):
File "main.py", line 15, in <module>
print(height(Node(4, Node(9, Node(1)))))
~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "main.py", line 11, in height
return 1 + max(height(node.left), height(node.right))
~~~~~~^^^^^^^^^^^
File "main.py", line 11, in height
return 1 + max(height(node.left), height(node.right))
~~~~~~^^^^^^^^^^^^
File "main.py", line 9, in height
if node.left is None and node.right is None:
^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'left'The first tree works, because every node in it has two children or none. In the second, 4 and 9 each have a left child only. Neither is a leaf, so height calls itself for both children of each, and the call for the missing right child of 9 gets None, which has no left. Interview tests like a node with one child for exactly this reason. Checking each child before its call (if node.left is not None:) works, but it needs a check in front of every call and still fails on an empty tree. Handle None once, at the top, and the function works for leaves, for nodes with one child and for the empty tree alike.
What it costs
Each function makes one call for every node and one for every None below a node, and does O(1) work in each: O(n) time for n nodes. The memory goes to the calls that are waiting for an answer, which are the nodes on the path from the root to the current node: O(h) extra memory, where h is the height. A balanced tree, in which the two subtrees of every node have about the same height, has a height of about log₂ n: 20 levels hold a million nodes. A tree in which every node has one child is a chain with h = n, and there the waiting calls run into a limit:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
chain = None
for value in range(2000):
chain = Node(value, chain)
print(height(chain))Traceback (most recent call last):
File "main.py", line 17, in <module>
print(height(chain))
~~~~~~^^^^^^^
File "main.py", line 11, in height
return 1 + max(height(node.left), height(node.right))
~~~~~~^^^^^^^^^^^
File "main.py", line 11, in height
return 1 + max(height(node.left), height(node.right))
~~~~~~^^^^^^^^^^^
File "main.py", line 11, in height
return 1 + max(height(node.left), height(node.right))
~~~~~~^^^^^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceededThe loop builds the chain from the bottom up, each new node taking the chain so far as its left child: 2,000 levels, and no recursion. But height keeps a call waiting for every level, and Python stops at about 1000 waiting calls with a RecursionError. So recursion is safe on balanced trees, which are never deep, and on small trees. Interviewers like to ask about this, and the next steps show how to walk a deep tree with a loop and a stack or a queue of your own.
Linked lists
A chain is a list in disguise. Give each node a single link, next, and you have a linked list, an interview favorite. The list is known by its first node, the head, and the last node's next is None. A linked list adds a node at its front in O(1), where a list's insert(0, x) is O(n), but reaching the k-th node takes k steps: there's no head[k]. Its classic questions are loops that follow the links, each O(n) time and O(1) memory:
class ListNode:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def reverse(head):
prev = None
node = head
while node is not None:
nxt = node.next
node.next = prev
prev = node
node = nxt
return prev
def middle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
head = None
for value in [5, 4, 3, 2, 1]:
head = ListNode(value, head)
head = reverse(head)
print(head.value, head.next.value, middle(head).value, middle(None))
print(has_cycle(head))
loop = ListNode(1, ListNode(2, ListNode(3)))
loop.next.next.next = loop.next
print(has_cycle(loop))5 4 3 None
False
TrueThe loop builds 1, 2, 3, 4, 5 from the back, each new node in front of the old head, and reverse turns it into 5, 4, 3, 2, 1. Its nxt saves the rest of the list before node.next changes, and prev holds the part already reversed. middle and has_cycle use slow and fast pointers: slow moves one node at a time and fast two, so when fast reaches the end, slow is at the middle. (middle returns the node, so an empty list gives None.) loop goes 1, 2, 3, 2, 3 and on forever, so there fast never reaches an end: it goes round the loop and gains a node on slow at each step until they meet. slow is fast asks whether both are the same node, not whether their values are equal.