144. Binary Tree Preorder Traversal

Problem Description

In this problem, we are asked to perform a preorder traversal on a binary tree. Preorder traversal is a type of depth-first traversal where each node is processed before its children. Specifically, the order of traversal is:

1. Visit (process) the root node.
2. Traverse the left subtree in preorder.
3. Traverse the right subtree in preorder.

The challenge here is to implement a function that takes the root node of a binary tree as input and returns a list of the node values in the order they were visited during the preorder traversal.

Intuition

The given solution uses the Morris traversal algorithm, which is an efficient way to perform tree traversals without recursion and without a stack (thus using O(1) extra space). The key idea behind Morris traversal is to use the tree's structure to create temporary links that allow returning to previous nodes, essentially replacing the function call stack with in-tree threading. Here's a step-by-step intuition for how the provided solution works:

1. Start at the root node.
2. If the current node has no left child, process the current node's value (in this case, append to the ans list), then move to the right child.
3. If the current node does have a left child, find the rightmost node of the left child (which is the predecessor node in the inorder traversal).
4. If the right child of the predecessor node is None, create a temporary threaded link from the predecessor to the current node, process the current node's value, and move to the left child of the current node.
5. If the right child of the predecessor node is the current node, it means we've returned to the current node after processing its left subtree. In this case, break the temporary link and move to the right child of the current node.
6. Repeat this process until all nodes have been visited.

This approach allows nodes to be visited in the correct preorder sequence without extra space or recursive function calls.

Learn more about Stack, Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The provided Python code implements the Morris traversal algorithm, which is one of the few approaches to perform a tree traversal. Here, we'll break down this implementation and also refer to the other approaches mentioned in the Reference Solution Approach:

1. Recursive Traversal: This is the simplest and most straightforward approach, where the function calls itself to visit nodes in the correct order. However, this could lead to a stack overflow if the tree is very deep since it requires space proportional to the height of the tree.

2. Non-recursive using Stack: Instead of system call stack in recursion, an explicit stack is used to simulate the recursion. The stack stores the nodes of the tree still to be visited. This approach does not have the stack overflow issue but still requires space proportional to the height of the tree.

3. Morris Traversal: As used in the provided solution, Morris traversal is an optimization over the recursive and stack approach that uses no additional space (O(1) space complexity). The algorithm works by establishing a temporary link known as a thread for finding the predecessor of the current node. The detailed steps are as follows:

   • Begin at the root node.
   • While the current node is not None:
     • If the current node has no left child, output the current node value and move to its right child.
     • If the current node has a left child, find its inorder predecessor in the left subtree—the rightmost node in the left subtree.
     • If the inorder predecessor has its right link as None, this means we haven't yet visited this part of the tree. Link it with the current node, output the current node's value, and move to the left child to continue the traversal.
     • If the inorder predecessor's right link points to the current node, this means we've finished visiting the left subtree and returned to the current node. Therefore, remove the temporary link (set it back to None), and move to the right child to continue traversal.
   • Repeat the above steps until all nodes are visited.

The ans list accumulates the values of the nodes in the preorder traversal order. The sign that a left subtree has been processed is that you arrive back at a node whose left subtree's rightmost node has a right child pointing back to it — in other words, a node you have created a temporary threaded link to earlier.

Overall, the Morris Traversal implementation is an elegant way to walk through the binary tree without additional space, making it extremely useful for memory-limited environments.

Example Walkthrough

Let's illustrate the Morris traversal algorithm using a small binary tree.

Consider the following binary tree:

1      1
2     / \
3    /   \
4   2     3
5  /     / \
6 /     4   5
76

The preorder traversal of this tree should give us the node values in the sequence 1, 2, 6, 3, 4, 5. Here's how the Morris traversal would process this tree:

1. Begin at the root node, which is 1. There is a left child, so we look for the rightmost node in the left subtree of 1 (which is node 6).
2. Node 6 doesn't have a right child, so we create a temporary link from node 6 back to node 1, process 1 by adding it to the ans list (ans = [1]), and move left to node 2.
3. At node 2, again, we have a left child, so we look for the rightmost node in the left subtree of 2, which is node 6.
4. Since the right child of 6 points back to node 1, we remove this link and move to the right child of 1, which is 3.
5. Since 2 has no right child, we process 2 (ans = [1, 2]) and then follow the temporary link back to node 1.
6. We've returned to node 1, and node 2 has been processed. We remove the temporary link (from 6 to 1) and move to the right child of 1, which is node 3.
7. We arrive at node 3, and it has a left child, so we look for the rightmost node in the left subtree of 3, which is 4 having no right child.
8. Create a temporary link from 4 back to 3, process 3 by adding it to the ans list (ans = [1, 2, 3]), and move to the left child, which is node 4.
9. Visit node 4, there's no left child, so process 4 (ans = [1, 2, 3, 4]) and move to its right, which is None.
10. We arrive at a None node, so we return to the previous node (3) via the temporary thread. Now we are at node 3 again, and the link from 4 to node 3 indicates we have processed the left subtree of 3.
11. We remove the temporary link from 4 back to 3, process node 4 (ans = [1, 2, 3, 4] remains unchanged as 4 was already processed), and move to the right child of 3, which is 5. Process 5 (ans = [1, 2, 3, 4, 5]).
12. Since 4 and 5 have no left children, and we've already processed 3, we finish our traversal.

By the end of this process, our ans list is [1, 2, 3, 4, 5]. However, we missed processing node 6 because the description lacked detailed return steps to the root after visiting leftmost nodes. But following the Morris traversal algorithm rigorously, node 6 would be processed after step 5 before returning to 1 (ans = [1, 2, 6, 3, 4, 5]).

The final output of the preorder traversal using Morris algorithm is [1, 2, 6, 3, 4, 5].

Solution Implementation

Time and Space Complexity

The given Python code is an implementation of the Morris Preorder Tree Traversal algorithm. Let's analyze the time complexity and space complexity of the code:

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because each edge in the tree is traversed at most twice: once when searching for the predecessor and once when moving back to the right child. Since there are n - 1 edges for n nodes, and each edge is traversed no more than twice, this leads to a linear time complexity.

Space Complexity

The space complexity of the Morris traversal algorithm is O(1). This algorithm modifies the tree by adding temporary links to the predecessor nodes but it does not use any additional data structures like stacks or recursion that depend on the number of nodes in the tree. Hence, it requires a constant amount of additional space.

Learn more about how to find time and space complexity quickly using problem constraints.