I am trying to implement the Morris Traversal of a Binary Tree in C++ for the "Binary Tree Preorder Traversal" problem on Leetcode. My code is failing on the test case: [3, 2, 1], where 3 is the root node, 1 is the left child, and 2 is the right child. I find that when I uncomment the two commented lines in the preorderTraversal method, the code works fine. As far as I can tell, the two commented lines are unnecessary for the solution, so I am not sure why they are causing an error.
/**
* 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) {}
* };
*/
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vals;
while (root != nullptr) {
if (root->left == nullptr) {
vals.push_back(root->val);
root = root->right;
} else {
TreeNode* last = root->left;
while (last->right != nullptr) last = last->right;
last->right = root->right;
//TreeNode* temp = root; NOT INCLUDING THIS CAUSES ERROR
vals.push_back(root->val);
root = root->left;
//temp->left = NULL; NOT INCLUDING THIS CAUSES ERROR
}
}
return vals;
}
This is the error that was thrown:
Runtime Error Message:
=================================================================
==24==ERROR: AddressSanitizer: heap-use-after-free on address 0x6030000003d8 at pc 0x00000038f4f5 bp 0x7ffd36eee010 sp 0x7ffd36eee008
READ of size 8 at 0x6030000003d8 thread T0
#4 0x7f4383a9e082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x6030000003d8 is located 8 bytes inside of 24-byte region [0x6030000003d0,0x6030000003e8)
freed by thread T0 here:
#5 0x7f4383a9e082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
previously allocated by thread T0 here:
#4 0x7f4383a9e082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
Shadow bytes around the buggy address:
0x0c067fff8020: fd fd fd fa fa fa fd fd fd fa fa fa fd fd fd fa
0x0c067fff8030: fa fa fd fd fd fa fa fa fd fd fd fa fa fa fd fd
0x0c067fff8040: fd fa fa fa fd fd fd fa fa fa fd fd fd fa fa fa
0x0c067fff8050: fd fd fd fa fa fa fd fd fd fa fa fa fd fd fd fa
0x0c067fff8060: fa fa fd fd fd fa fa fa fd fd fd fa fa fa 00 00
=>0x0c067fff8070: 00 fa fa fa fd fd fd fa fa fa fd[fd]fd fa fa fa
0x0c067fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff80a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff80b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff80c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==24==ABORTING
This error does not occur in your code, but in the LeetCode testing code that calls your function. We can reproduce it with this tree:
┌─────┐
│ 1 │
└┬───┬┘
┌─◄┘ └►─┐
┌──┴──┐ ┌──┴──┐
│ 2 │ │ 3 │
└┬────┘ └─────┘
┌─◄┘
┌──┴──┐
│ 4 │
└─────┘
When your function returns, it leaves the tree in this state:
┌─────┐
│ 1 │
└┬───┬┘
┌─◄┘ └►─┐
┌──┴──┐ ┌──┴──┐
│ 2 │ ┌─┤ 3 │
└┬───┬┘ │ └─────┘
┌─◄┘ └►─┤
┌──┴──┐ │
│ 4 │ │
└────┬┘ │
└─────►─┘
After LeetCode has verified the returned vector it cleans up the memory allocated by the tree, and that is where the problem occurs. It will delete node 3 a second time, not expecting that this node has more than one parent. At the second delete operation, the exception occurs.
To avoid this from happening, you need to make sure to leave the tree in a state where it really is a tree: nodes should have at the most one parent.
Even the commented statements do not ensure that the tree is restored completely. In fact, it leaves the left pointer of the root node (and other nodes) set to NULL, which means that some subtrees are no longer reachable from the root node, and the LeetCode framework cannot completely clean up the memory used by the tree. So although the exception no longer occurs, it is not a clean solution.
A Morris traversal will use a node's right pointer that is initially null to temporary store a pointer to the node's ancestor that is its inorder successor.
Here is an implementation that will have restored the tree correctly once all nodes have been visited:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vals;
while (root) {
if (!root->left) {
vals.push_back(root->val);
root = root->right;
} else {
// Find the node's predecessor in its left subtree
TreeNode* last = root->left;
while (last->right && last->right != root) {
last = last->right;
}
if (last->right == root) { // Cycle! This is a temporary pointer.
last->right = nullptr; // Restore the memory that was temporarily used
root = root->right; // The left subtree has been visited, focus on right subtree
} else {
last->right = root; // Temporarily use this memory to point to successor (ancestor)
vals.push_back(root->val);
root = root->left; // Visit left subtree -- we will eventually visit "last" there
}
}
}
return vals;
}
};