Morris traversal for Preorder
Morris Traversal is a special method for traversing binary trees without using recursion or an explicit stack. It allows us to perform both in-order and pre-order traversals of a binary tree using only constant space while maintaining the original structure of the tree. The algorithm was introduced by J. H. Morris in 1979.
Problem Statement
Given a binary tree, we want to perform a pre-order traversal using the Morris Traversal technique. The goal is to print the values of the nodes in pre-order sequence.
Description
The Morris Traversal algorithm is based on the idea of threaded binary trees, where we temporarily modify the structure of the tree to create threads connecting some nodes. These threads help us traverse the tree without using a stack or recursion.
Let's understand the algorithm with an example:
Consider the binary tree:
4
/ \
8 10
/ \ / \
1 6 7 -3
/
9
Idea to Solve the Problem
- Start with the root node.
- Initialize the current node as the root.
- While the current node is not null: a. If the current node doesn't have a left child, print its value and move to the right child. b. If the current node has a left child: i. Find the rightmost node in the left subtree of the current node. ii. If the rightmost node doesn't have a threaded connection to the current node, establish a thread connection from it to the current node and print the current node's value. Move to the left child. iii. If a thread connection already exists, remove the thread connection and move to the right child.
Pseudocode
MorrisPreorder(root):
current = root
while current is not null:
if current's left child is null:
print current's value
current = current's right child
else:
auxiliary = current's left child
while auxiliary's right child is not null and auxiliary's right child is not current:
auxiliary = auxiliary's right child
if auxiliary's right child is null:
print current's value
auxiliary's right child = current
current = current's left child
else:
auxiliary's right child = null
current = current's right child
Algorithm Explanation
- Start with the root node. Initialize
current
as the root node. - Traverse the tree using a
while
loop untilcurrent
becomes null. Inside the loop:
a. If the current node doesn't have a left child, print its value and move to the right child.
b. If the current node has a left child:
i. Start with
auxiliary
as the left child of the current node.ii. Find the rightmost node in the left subtree by moving right until the right child of
auxiliary
is null or points back to the
current
node.iii. If the right child of the
auxiliary
node is null:- Print the value of the
current
node.- Establish a thread connection by setting the right child of
auxiliary
tocurrent
.- Move to the left child.
iv. If the right child of
auxiliary
is thecurrent
node (indicating a threaded connection):- Remove the thread connection by setting the right child of
auxiliary
to null.- Move to the right child.
Code Solution
-
1) Morris preorder traversal in java
2) Morris preorder traversal in c++
3) Morris preorder traversal in c
4) Morris preorder traversal in golang
5) Morris preorder traversal in c#
6) Morris preorder traversal in vb.net
7) Morris preorder traversal in php
8) Morris preorder traversal in node js
9) Morris preorder traversal in typescript
10) Morris preorder traversal in python
11) Morris preorder traversal in ruby
12) Morris preorder traversal in scala
13) Morris preorder traversal in kotlin
14) Morris preorder traversal in swift
Time Complexity
The Morris Traversal algorithm has a time complexity of O(n) where n is the number of nodes in the binary tree. This is because each edge of the tree is traversed exactly twice: once while establishing the thread connections and once while removing them.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment