Everything about Tree traversal- Inorder, preorder, postorder, time complexity with code
Definition
Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees.
In [21]:
# A class that represents an individual node in a
# Binary Tree
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.data = key
Ways of traversals
Trees are traversed in the following ways:
- Depth First Traversals:
- Inorder (Left, Root, Right) : 4 2 5 1 3
- Preorder (Root, Left, Right) : 1 2 4 5 3
- Postorder (Left, Right, Root) : 4 5 2 3 1
- Breadth-First or Level Order Traversal: 1 2 3 4 5
In [22]:
# Function to perform inorder traversal on the BST
def inorder(root):
if root is None:
return inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
Inorder Traversal
Explanation
- Traverse the left subtree, i.e., call Inorder(left-subtree)
- Visit the root.
- Traverse the right subtree, i.e., call Inorder(right-subtree)
A new key is always inserted at the leaf. We start searching a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
Time Complexity
O(n)
Let us see different corner cases. Complexity function T(n) — for all problems where tree traversal is involved — can be defined as: T(n) = T(k) + T(n — k — 1) + c Where k is the number of nodes on one side of the root and n-k-1 on the other side. Let’s do an analysis of boundary conditions Case 1: Skewed tree (One of the subtrees is empty and another subtree is non-empty ) k is 0 in this case. T(n) = T(0) + T(n-1) + c T(n) = 2T(0) + T(n-2) + 2c T(n) = 3T(0) + T(n-3) + 3c T(n) = 4T(0) + T(n-4) + 4c ………………………………………… …………………………………………. T(n) = (n-1)T(0) + T(1) + (n-1)c T(n) = nT(0) + (n)c Value of T(0) will be some constant say d. (traversing an empty tree will take some constants time) T(n) = n(c+d) T(n) = Θ(n) (Theta of n) Case 2: Both left and right subtrees have an equal number of nodes. T(n) = 2T(|n/2|) + c This recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method http://en.wikipedia.org/wiki/Master_theorem. If we solve it by master method we get (-)(n)
Space Complexity
If we don’t consider the size of the stack for function calls then O(1). Otherwise, O(h) where h is the height of the tree.
The height of the skewed tree is n (no. of elements) so the worst space complexity is O(n). Height is (Log n) for the balanced tree so the best space complexity is O(Log n).
Uses In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal s reversed can be used.
Example: In order traversal for the above-given figure is 4 2 5 1 3.
Inorder Traversal
Explanation
- Traverse the left subtree, i.e., call Inorder(left-subtree)
- Visit the root.
- Traverse the right subtree, i.e., call Inorder(right-subtree)
A new key is always inserted at the leaf. We start searching a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
Time Complexity
O(n)
Let us see different corner cases. Complexity function T(n) — for all problems where tree traversal is involved — can be defined as: T(n) = T(k) + T(n — k — 1) + c Where k is the number of nodes on one side of the root and n-k-1 on the other side. Let’s do an analysis of boundary conditions Case 1: Skewed tree (One of the subtrees is empty and another subtree is non-empty ) k is 0 in this case. T(n) = T(0) + T(n-1) + c T(n) = 2T(0) + T(n-2) + 2c T(n) = 3T(0) + T(n-3) + 3c T(n) = 4T(0) + T(n-4) + 4c ………………………………………… …………………………………………. T(n) = (n-1)T(0) + T(1) + (n-1)c T(n) = nT(0) + (n)c Value of T(0) will be some constant say d. (traversing an empty tree will take some constants time) T(n) = n(c+d) T(n) = Θ(n) (Theta of n) Case 2: Both left and right subtrees have an equal number of nodes. T(n) = 2T(|n/2|) + c This recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method http://en.wikipedia.org/wiki/Master_theorem. If we solve it by master method we get (-)(n)
Space Complexity
If we don’t consider the size of the stack for function calls then O(1). Otherwise, O(h) where h is the height of the tree.
The height of the skewed tree is n (no. of elements) so the worst space complexity is O(n). Height is (Log n) for the balanced tree so the best space complexity is O(Log n).
Uses In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal s reversed can be used.
Example: In order traversal for the above-given figure is 4 2 5 1 3.
In [23]:
# A function to do inorder tree traversal
def printInorder(root):
if root:
# First recur on left child
printInorder(root.left)
# then print the data of node
print(root.data),
# now recur on right child
printInorder(root.right)
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)print ("\nThe Inorder traversal of binary tree is")
printInorder(root)The Inorder traversal of binary tree is
4
2
5
1
3
PreOrder Traversal
Explanation
- Visit the root.
- Traverse the left subtree, i.e., call PreOrder(left-subtree)
- Traverse the right subtree, i.e., call PreOrder(right-subtree)
Time Complexity
O(n)
Let us see different corner cases. Complexity function T(n) — for all problems where tree traversal is involved — can be defined as: T(n) = T(k) + T(n — k — 1) + c Where k is the number of nodes on one side of the root and n-k-1 on the other side. Let’s do an analysis of boundary conditions Case 1: Skewed tree (One of the subtrees is empty and another subtree is non-empty ) k is 0 in this case. T(n) = T(0) + T(n-1) + c T(n) = 2T(0) + T(n-2) + 2c T(n) = 3T(0) + T(n-3) + 3c T(n) = 4T(0) + T(n-4) + 4c ………………………………………… …………………………………………. T(n) = (n-1)T(0) + T(1) + (n-1)c T(n) = nT(0) + (n)c Value of T(0) will be some constant say d. (traversing an empty tree will take some constants time) T(n) = n(c+d) T(n) = Θ(n) (Theta of n) Case 2: Both left and right subtrees have an equal number of nodes. T(n) = 2T(|n/2|) + c This recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method http://en.wikipedia.org/wiki/Master_theorem. If we solve it by master method we get (-)(n)
Space Complexity
If we don’t consider the size of the stack for function calls then O(1). Otherwise, O(h) where h is the height of the tree.
The height of the skewed tree is n (no. of elements) so the worst space complexity is O(n). Height is (Log n) for the balanced tree so the best space complexity is O(Log n).
Uses
Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on an expression tree. Please see http://en.wikipedia.org/wiki/Polish_notation know why prefix expressions are useful.
Example: Preorder traversal for the above-given figure is 1 2 4 5 3.
In [24]:
# A function to do preorder tree traversal
def printPreorder(root):
if root:
# First print the data of node
print(root.data),
# Then recur on left child
printPreorder(root.left)
# Finally recur on right child
printPreorder(root.right)
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)print ("\nThe Inorder traversal of binary tree is")
printPreorder(root)The Inorder traversal of binary tree is
1
2
4
5
3
In [25]:
# A function to do postorder tree traversal
def printPostorder(root):
if root:
# First recur on left child
printPostorder(root.left)
# the recur on right child
printPostorder(root.right)
# now print the data of node
print(root.data),
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)print ("\nThe Inorder traversal of binary tree is")
printPostorder(root)The Inorder traversal of binary tree is
4
5
2
3
1
Breadth first traversal
Methods
- Use function to print a current level
- Using queue
Method 1 (Use function to print a current level)
Expatiation
There are basically two functions in this method. One is to print all nodes at a given level (printCurrentLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printCurrentLevel to print nodes at all levels one by one starting from the root.
Time Complexity
O(n²) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n²).
Space Complexity
O(n) in worst case. For a skewed tree, printGivenLevel() uses O(n) space for call stack. For a Balanced tree, the call stack uses O(log n) space, (i.e., the height of the balanced tree).
In [26]:
# Recursive Python program for level
# Function to print level order traversal of tree
def printLevelOrder(root):
h = height(root)
for i in range(1, h+1):
printCurrentLevel(root, i)
# Print nodes at a current level
def printCurrentLevel(root, level):
if root is None:
return
if level == 1:
print(root.data, end=" ")
elif level > 1:
printCurrentLevel(root.left, level-1)
printCurrentLevel(root.right, level-1)
""" Compute the height of a tree--the number of nodes
along the longest path from the root node down to
the farthest leaf node
"""
def height(node):
if node is None:
return 0
else:
# Compute the height of each subtree
lheight = height(node.left)
rheight = height(node.right) # Use the larger one
if lheight > rheight:
return lheight+1
else:
return rheight+1
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)print("Level order traversal of binary tree is -")
printLevelOrder(root)Level order traversal of binary tree is -
1 2 3 4 5
Method 2 (Using queue)
Expatiation
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.
Time Complexity
O(n²) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n²).
Space Complexity
O(n) in worst case. For a skewed tree, printGivenLevel() uses O(n) space for call stack. For a Balanced tree, the call stack uses O(log n) space, (i.e., the height of the balanced tree).
In [27]:
# order traversal using Queue
def printLevelOrder(root):
# Base Case
if root is None:
return # Create an empty queue
# for level order traversal
queue = [] # Enqueue Root and initialize height
queue.append(root) while len(queue) > 0: # Print front of queue and
# remove it from queue
print(queue[0].data)
node = queue.pop(0) # Enqueue left child
if node.left is not None:
queue.append(node.left) # Enqueue right child
if node.right is not None:
queue.append(node.right)# Function to print level order traversal of tree
def printLevelOrder(root):
h = height(root)
for i in range(1, h+1):
printCurrentLevel(root, i)
# Driver Program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)print("Level Order Traversal of binary tree is -")
printLevelOrder(root)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)Level Order Traversal of binary tree is -
1 2 3 4 5Complete code: https://github.com/praharshbhatt/ds_algo_leetcode/blob/master/notes/concepts/tree_traversals/tree_traversals.ipynb
