Morris traversal for Inorder
Morris Traversal is a method to traverse a binary tree without using the stack or recursion, and it does so with constant extra space. In this post, we will explore the Morris Traversal algorithm for inorder traversal of a binary tree and provide an explanation along with examples and code.
Problem Statement
The problem we are trying to solve is to traverse a binary tree in the inorder fashion using the Morris Traversal technique. We want to achieve this traversal without using additional space for stack or recursion.
Example
Consider the binary tree provided in the code:
4
/ \
8 3
/ \ / \
1 6 7 2
/
9
The inorder traversal of this tree should result in: 1 8 9 6 4 7 3 2
Idea to Solve
The main idea behind Morris Traversal is to use threaded binary trees. In a threaded binary tree, the right pointers of some nodes are made to point to the inorder successor (the node that would be visited next in an inorder traversal). This threading allows us to navigate the tree without using extra space while maintaining the ability to backtrack to the parent nodes.
Algorithm
- Initialize
current
as the root of the tree. - While
current
is not null:- If
current
has no left child:- Print the value of
current
. - Move
current
to its right child.
- Print the value of
- If
current
has a left child:- Find the rightmost node in the left subtree of
current
. This node will be the inorder predecessor ofcurrent
. - If the right child of this predecessor is null, set it to
current
and movecurrent
to its left child. - If the right child is already
current
, it means we've visited the left subtree. Print the value ofcurrent
, revert the right child of the predecessor back to null, and movecurrent
to its right child.
- Find the rightmost node in the left subtree of
- If
- Repeat step 2 until
current
becomes null.
Pseudocode
1. Initialize current as root
2. while current is not null:
if current.left is null:
print current.data
current = current.right
else:
find the rightmost node in current's left subtree (predecessor)
if predecessor.right is null:
predecessor.right = current
current = current.left
else:
print current.data
predecessor.right = null
current = current.right
Code Solution
-
1) Morris inorder traversal in java
2) Morris inorder traversal in c++
3) Morris inorder traversal in c
4) Morris inorder traversal in golang
5) Morris inorder traversal in c#
6) Morris inorder traversal in php
7) Morris inorder traversal in node js
8) Morris inorder traversal in python
9) Morris inorder traversal in ruby
10) Morris inorder traversal in scala
11) Morris inorder traversal in swift
12) Morris inorder traversal in kotlin
13) Morris inorder traversal in typescript
14) Morris inorder traversal in vb.net
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 is traversed at most twice - once when establishing the threaded connections and once when following those connections.
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