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.

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.

💪
Level Up Your
Algo Skills

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].

Python Solution

1# A binary tree node has a value, and references to left and right child nodes.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
10        # This is the result list that will contain the values of nodes visited.
11        result = []
12      
13        # Loop over the tree nodes until we visited all of them.
14        while root:
15            # If there is no left child, we can visit this node and move to right.
16            if root.left is None:
17                result.append(root.val)
18                root = root.right
19            else:
20                # Find the inorder predecessor of the current node.
21                predecessor = root.left
22                # Move to the rightmost child of the left subtree.
23                while predecessor.right and predecessor.right != root:
24                    predecessor = predecessor.right
25              
26                # If the rightmost node of left subtree is not linked to current node.
27                if predecessor.right is None:
28                    # Link it to the current node and visit the current node.
29                    result.append(root.val)
30                    predecessor.right = root
31                    # Move to the left child of the current node.
32                    root = root.left
33                else:
34                    # If it's already linked, it means we've finished the left subtree.
35                    # Unlink the predecessor and move to the right child of the node.
36                    predecessor.right = None
37                    root = root.right
38      
39        # Return the result list.
40        return result
41

Java Solution

1import java.util.List;
2import java.util.ArrayList;
3
4// Definition for a binary tree node.
5class TreeNode {
6    int value;
7    TreeNode left;
8    TreeNode right;
9  
10    TreeNode() {}
11    TreeNode(int value) { this.value = value; }
12    TreeNode(int value, TreeNode left, TreeNode right) {
13        this.value = value;
14        this.left = left;
15        this.right = right;
16    }
17}
18
19public class Solution {
20  
21    /**
22     * Performs a preorder traversal of a binary tree and returns
23     * the visited nodes values in a list.
24     *
25     * @param root the root node of the binary tree
26     * @return a list of integers representing the node values in preorder
27     */
28    public List<Integer> preorderTraversal(TreeNode root) {
29        List<Integer> result = new ArrayList<>();
30        while (root != null) {
31            if (root.left == null) {
32                // If there is no left child, add the current node value
33                // and move to the right node
34                result.add(root.value);
35                root = root.right;
36            } else {
37                // Find the inorder predecessor of the current node
38                TreeNode predecessor = root.left;
39                while (predecessor.right != null && predecessor.right != root) {
40                    predecessor = predecessor.right;
41                }
42              
43                // If the right child of the inorder predecessor is null, we
44                // set it to the current node and move to the left child of
45                // the current node after recording it.
46                if (predecessor.right == null) {
47                    result.add(root.value);
48                    predecessor.right = root;
49                    root = root.left;
50                } else {
51                    // If the right child is already pointing to the current node,
52                    // we are visiting the node again, so we restore the tree structure
53                    // by setting the right child of the predecessor to null and move
54                    // to the right child of the current node as we've finished traversing
55                    // the left subtree due to Morris traversal.
56                    predecessor.right = null;
57                    root = root.right;
58                }
59            }
60        }
61        return result;
62    }
63}
64

C++ Solution

1#include <vector>
2using namespace std;
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    vector<int> preorderTraversal(TreeNode* root) {
16        vector<int> result; // This vector will hold the preorder traversal result
17
18        while (root != nullptr) { // Continue until there are no more nodes to visit
19            if (root->left == nullptr) { 
20                // If there is no left child, visit this node and move to the right child
21                result.push_back(root->val);
22                root = root->right;
23            } else { 
24                // If there is a left child, find the rightmost node of the
25                // left subtree or a previously created link to the current node
26                TreeNode* previous = root->left;
27                while (previous->right != nullptr && previous->right != root) {
28                    previous = previous->right;
29                }
30
31                if (previous->right == nullptr) {
32                    // Establish a temporary link back to the current node
33                    // so we can return after exploring left subtree
34                    result.push_back(root->val); // Visit the current node
35                    previous->right = root; // Make link to go back to root after left subtree is done
36                    root = root->left; // Move to the left subtree
37                } else {
38                    // Left subtree has been visited, remove the link
39                    previous->right = nullptr;
40                    // Move to the right subtree
41                    root = root->right;
42                }
43            }
44        }
45        return result; // Return the result of preorder traversal
46    }
47};
48

Typescript Solution

1/**
2 * Performs a preorder traversal on a binary tree without using recursion or a stack.
3 * 
4 * @param {TreeNode | null} root - The root node of the binary tree.
5 * @returns {number[]} The preorder traversal output as an array of node values.
6 */
7function preorderTraversal(root: TreeNode | null): number[] {
8    // Initialize the output array to store the preorder traversal sequence
9    let result: number[] = [];
10
11    // Iterate while there are nodes to visit
12    while (root !== null) {
13        if (root.left === null) {
14            // If there is no left child, push the current node's value and move to right child
15            result.push(root.val);
16            root = root.right;
17        } else {
18            // Find the rightmost node of the left subtree or the predecessor of the current node
19            let predecessor = root.left;
20            while (predecessor.right !== null && predecessor.right !== root) {
21                predecessor = predecessor.right;
22            }
23
24            // If the right subtree of the predecessor is not yet linked to the current node
25            if (predecessor.right === null) {
26                // Record the current node's value (as part of preorder)
27                result.push(root.val);
28                // Link the predecessor's right to the current node to create a temporary threaded binary tree
29                predecessor.right = root;
30                // Move to the left child to continue traversal
31                root = root.left;
32            } else {
33                // If the right subtree is already linked to the current node, remove that temporary link
34                predecessor.right = null;
35                // Move to the right child to continue traversal since the left subtree is already processed
36                root = root.right;
37            }
38        }
39    }
40
41    // Return the result array with the traversal sequence
42    return result;
43}
44

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫