Binary Tree Inorder Traversal
Easy · Trees · Explanation and code example
Morris Traversal
How it works
Morris Traversal achieves O(1) extra space by temporarily modifying the tree structure. The idea is to create a temporary link from the rightmost node of the left subtree back to the current node. This allows us to return to the current node after traversing the left subtree without using a stack. After processing, we remove the temporary link to restore the original tree.
Steps
- Initialize the current node to the root.
- While the current node is not
null:- If the current node has no left child, add its value to the result and move to the right child.
- Otherwise, find the rightmost node in the left subtree (the inorder predecessor).
- If the predecessor's right pointer is
null, set it to the current node (create a thread) and move to the left child. - If the predecessor's right pointer already points to the current node, remove the thread, add the current node's value to the result, and move to the right child.
- Return the result list.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)extra space.O(n)space for the output array.
Things to watch for
Wrong Order of Operations in Recursion
Inorder traversal requires visiting left, then current, then right. A common mistake is adding the current node's value before or after both recursive calls, which produces preorder or postorder results instead.
Forgetting to Move Right in Iterative Approach
After popping and processing a node from the stack, you must move to its right child. Forgetting cur = cur.right causes an infinite loop since the same node keeps getting processed.
Python code example
from typing import List, Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
cur = root
while cur:
if not cur.left:
res.append(cur.val)
cur = cur.right
else:
prev = cur.left
while prev.right and prev.right != cur:
prev = prev.right
if not prev.right:
prev.right = cur
cur = cur.left
else:
prev.right = None
res.append(cur.val)
cur = cur.right
return res
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* cur = root;
while (cur) {
if (!cur->left) {
res.push_back(cur->val);
cur = cur->right;
} else {
TreeNode* prev = cur->left;
while (prev->right && prev->right != cur) {
prev = prev->right;
}
if (!prev->right) {
prev->right = cur;
cur = cur->left;
} else {
prev->right = nullptr;
res.push_back(cur->val);
cur = cur->right;
}
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.