Pre-order: root, left, right – F, B, A, D, C, E, G, I, H
Recursive Implementation:
The recursive implementation is quite simple and intuitive. We process the root and then its left and right children until there are no nodes left, recursively.
def preorderTraversal(self, root: TreeNode) -> List[int]:
nodes = []
def preorder(root):
if root:
nodes.append(root.val)
preorder(root.left)
preorder(root.right)
preorder(root)
return nodes
Iterative Implementation:
What happens beneath recursion is the use of stack space to store nodes. In the iterative implementation, we can explicitly mimic the use of stack. Note that we need to process the root, the left child and then the right child. In stacks, the rule is Last In First Out (LIFO) or First In Last Out (FILO). This means, to process the left node before the right node in pre-order, we have to add the right node to the stack before adding the left node. See the code below.
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
nodes, stack = [], [root]
while stack:
curr = stack.pop()
nodes.append(curr.val)
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return nodes
In-order: left, root, right – A, B, C, D, E, F, G, H, I
Recursive Implementation:
This is very similar to pre-order traversal except that we process the left node before the root and then the right child.
def inorderTraversal(self, root: TreeNode) -> List[int]:
nodes = []
def inorder(root):
if root:
inorder(root.left)
nodes.append(root.val)
inorder(root.right)
inorder(root)
return nodes
Iterative Implementation:
The iterative implementation of in-order traversal is a little tricky. In in-order, we have to process the left node first and then the root followed by the right child. For this, we have to get to the left most node in the tree first which is the leftmost leaf node if it is present.
- Do this by using a pointer called curr which points to the root at first.
- Traverse the left subtree while adding nodes to the stack, setting curr = curr.left until there are no more nodes left which means until curr is NULL. This will capture the entire left subtree of a node.
- Once curr is NULL, start traversing the right subtree. Before traversing the right subtree, pop the stack and add the top most element to the nodes list.
- To traverse the right subtree, set curr = curr.right
Basically we keep going as left as possible from a given node until there are no more nodes left. We then pop the stack, add to the results and start traversing the right subtree of the node that we just processed. We keep repeating this process as long as curr is not NULL or the stack is not empty. I recommend that you hand simulate a simple example to understand how the algorithm works.
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
nodes, stack = [], []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
nodes.append(curr.val)
curr = curr.right
return nodes
Post-order: left, right, root – A, C, E, D, B, H, I, G, F
Recursive Implementation:
In post order, we process the left and right child before the root node, recursively.
def postorderTraversal(self, root: TreeNode) -> List[int]:
nodes = []
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
nodes.append(root.val)
postorder(root)
return nodes
Iterative Implementation:
In the post-order traversal implementation, we will take a simple approach where our stack contains the reverse of post order sequence. Once we are done processing, we will return the results by reversing the stack.
Note that in post-order, we need to return left, right and then root. The reverse of this is root, right and then left. This is the order in which we will be processing the nodes.
- To begin with, add the root to the stack.
- Pop the stack and add the top most element to nodes list.
- Add the left child of this node and then the right child to the stack. This will make sure that we pop and process the right child first and then the left child.
- Notice that the order of processing/ popping is root, right and then the left child which is the reverse of post-order traversal.
- Upon processing the whole tree, return the reverse of nodes list.
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
nodes = []
while stack:
node = stack.pop()
nodes.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return nodes[::-1]
Level-order: F, B, G, A, D, I, C, E, H
Level-order traversal is also known as Breadth First Search of a tree. For this we can use a queue usually but the code below uses a simple Python List to mimic the same functionality. Here level indicates the height of the tree. We go from root to the leaves level by level.
- Add root to a list/ queue called level.
- Add all the nodes at the top most level to the nodes list.
- Create a temp list and add the left and right child of each node in this level from left to right.
- Set level to this temp list to process the next level.
- Continue processing each level as long as there are nodes left.
Implementation:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
level = [root]
result = []
while level:
result.append([node.val for node in level])
temp = []
for node in level:
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right)
level = [node for node in temp]
return result
Time Complexity: The processing time for different traversals is O(N) where N is the number of nodes in the tree and we have to process all N nodes.
Space Complexity: O(N) for the use of stack/ queue space where N is the number of nodes in the tree.
Hope you enjoyed learning the implementations for different types of tree traversals.
That Girl Coder 