This post works best while listening to
Dogs.
Today let’s take a look at several ways to traverse a binary tree, both iteratively and recursively. Then, we’ll look at another algorithm that I think will make us all piddle a bit in our trousers.
As usual, we’ll be working with this TreeNode class implementation:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
And we’ll construct the following tree for each example:
1
/ \
/ \
2 3
/ \ \
/ \ \
4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right = TreeNode(3)
root.right.right = TreeNode(6)
Here are the three main ways of applying a depth-first search to order the nodes of a tree traversal that use a stack:
For each, I’ll post an iterative and a recursive solution.
Lastly, we’ll look at another algorithm that doesn’t use either a stack or recursion:
Preorder
Recursive
from Tree import TreeNode
def preorder(root, visited=[]):
if not root:
return
visited.append(root.value)
preorder(root.left, visited)
preorder(root.right, visited)
return visited
print(preorder(root))
# [1, 2, 4, 5, 3, 6]
- Time complexity: O(N)
- Space complexity: O(N)
Iterative
from Tree import TreeNode
def preorder(root):
stack = [root]
visited = []
while stack:
node = stack.pop()
visited.append(node.value)
if node.right: (1)
stack.append(node.right)
if node.left:
stack.append(node.left)
return visited
print(preorder(root))
# [1, 2, 4, 5, 3, 6]
Notes:
- Note that the order that we push nodes onto the stack is critical. The right node must be pushed on before the left node to maintain the correct order, as the left node will then be popped first.
- Time complexity: O(N)
- Space complexity: O(N)
Inorder
Recursive
from Tree import TreeNode
def inorder(root, visited=[]):
if not root:
return
inorder(root.left, visited)
visited.append(root.value)
inorder(root.right, visited)
return visited
print(inorder(root))
# [4, 2, 5, 1, 3, 6]
- Time complexity: O(N)
- Space complexity: O(N)
Iterative
from Tree import TreeNode
def inorder(root):
stack = [] (1)
current = root
visited = []
while current or stack:
while current: (2)
stack.append(current)
current = current.left
current = stack.pop() (3)
visited.append(current.value)
current = current.right (4)
return visited
print(inorder(root))
# [4, 2, 5, 1, 3, 6]
Notes:
- Unlike other iterative traversals, we don’t start with the root already in the stack.
- Traverse as far left as we can.
- Pop the leftmost node.
- Assume there’s a right node. If not, the next left node will be popped, and then we’ll again assume there’s a right node.
- Time complexity: O(N)
- Space complexity: O(N)
Postorder
Recursive
from Tree import TreeNode
def postorder(root, visited=[]):
if not root:
return
postorder(root.left)
postorder(root.right)
visited.append(root.value)
return visited
print(postorder(root))
# [4, 5, 2, 6, 3, 1]
- Time complexity: O(N)
- Space complexity: O(N)
Iterative
from Tree import TreeNode
# Iterative, a queue and a stack.
def postorder(root):
stack = [root] (1)
queue = []
while stack:
node = stack.pop()
queue.insert(0, node.value)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return queue
print(postorder(root))
# [4, 5, 2, 6, 3, 1]
Notes:
- This algorithm, unlike the others, uses both a stack and a queue.
- Time complexity: O(N)
- Space complexity: O(N)
Morris Traversal
This type of traversal can be used for preorder, inorder and postorder traversals.
Let’s now take a look at an implementation that does not use a stack or recursion to traverse the tree. This is the Morris traversal or threaded binary tree traversal. Though more advanced than the previous ways, it is well worth putting in the effort to understand how this works because it’s fucking cool.
So, the key to how this works is its way of backtracking to previous nodes. In the iterative version, we use a stack, pushing and popping and bipping and bopping, to get back to nodes higher in the tree structure (re: closer to the root) to process them. The recursive version uses a similar method, but one that’s “builtin” and doesn’t require us to allocate an additional data structure: the call stack.
Morris traversal, on the other hand, creates links or pointers to the previous nodes, obviating the need for a stack. For example, when traversing inorder, the algorithm creates a pointer from the inorder predecessor node to the root node. For the root node, the inorder predecessor is the rightmost node of its left subtree.
Let’s take a peek at some tree structures:
1 / / 2
The node with the value 2 is the inorder predecessor node of the root node with the value 1. The Morris traversal algorithm will create a pointer from node 2 to node 1.
1
/ \
/ \
2 3
/ \ \
/ \ \
4 5 6
The node with the value 5 is the inorder predecessor node of the root node with the value 1. The Morris traversal algorithm will create a pointer from node 5 to node 1.
Those aren’t the only pointers that are created, though. It will create a link for every inorder predecessor node that’s found in any left subtree.
Yes, this algorithm will temporarily mutate the tree, but it will clean up after itself and remove the pointers.
I’ve seen accepted solutions on at least one major coding site that doesn’t cleanup the tree after it’s been mutated. Don’t use this solution, it’s for chumps! Be a hero and revert the tree back to its original state.
from Tree import TreeNode
def inorder(root):
current = root
visited = []
while current:
if not current.left: (1)
visited.append(current.value)
current = current.right
else:
predecessor = current.left (2)
while predecessor.right and predecessor.right is not current: (3)
predecessor = predecessor.right
if not predecessor.right: (4)
predecessor.right = current
current = current.left
else:
predecessor.right = None (5)
visited.append(current.value)
current = current.right
return visited
print(inorder(root))
# [4, 2, 5, 1, 3, 6]
Notes:
- If not left, go right. This doesn’t mean that it won’t go left in future iterations. That is dependent upon the subtree of
current.right. - Find the inorder predecessor node. This is initially set to the
current.leftnode, which we know is present because we just checked for its existence. Recall that this is the node that will then have the pointer back to the root node. - We find the rightmost node of the left subtree. Note that it’s necessary to check that the
predecessor.rightis not thecurrentnode. This occurs when a link/pointer has already been established. If not for this check, we would get into an infinite loop. - If there is no
predecessor.rightnode, than we know two things:- We’re at the rightmost node of the left subtree. This is the inorder predecessor.
- We need to establish a new root. (Re-)Setting
currentwill allow us to look for more left subtrees with which to establish links.
- Sever the link by nulling out the pointer. This is how the cleanup occurs after we’ve traversed the subtree.
- Time complexity: O(N)
- Space complexity: O(1)