Binary Tree Preorder Traversal

class Solution {
public:
    vector<int> traversePreorder(TreeNode* root) {
        vector<int> result;
        TreeNode* current = root;
        while (current != nullptr) {
            if (current->left == nullptr) {
                result.push_back(current->val);
                current = current->right;
            } else {
                TreeNode* temp = current->left;
                while (temp->right != nullptr && temp->right != current) {
                    temp = temp->right;
                }
                if (temp->right == nullptr) {
                    result.push_back(current->val);
                    temp->right = current;
                    current = current->left;
                } else {
                    temp->right = nullptr;
                    current = current->right;
                }
            }
        }
        return result;
    }
};

The provided C++ code implements the Binary Tree Preorder Traversal using an iterative approach with the Morris Traversal technique. Here's how the function traversePreorder operates:

1. Initialize a vector<int> named result to store the values of the nodes as they are visited.
2. Start with the root node and use a pointer current to traverse the tree.
3. Enter a while loop which continues as long as current is not nullptr.
4. Inside the loop, check if the left child of current is nullptr:
   • If true, record the value of current into result.
   • Move current to its right child.
5. If the left child is not nullptr, find the rightmost node of the left subtree; this node will temporarily link back to current to avoid usage of stack or recursion.
6. Check if the temporary link (temp->right) is already created:
   • If temp->right is nullptr, make temp->right point to current (creating a temporary link), save the current node's value in the result vector, and move current to its left child.
   • If temp->right points to current, this means you're revisiting the node and should remove the temporary link and move current to its right child.
7. The loop ends when all nodes are visited, and current becomes nullptr.
8. Return the result vector containing the preorder traversal of the tree.

This approach is memory efficient as it does not use additional data structures like stack or recursion for maintaining tree traversal state, and it modifies the tree temporarily during traversal to achieve this.

class Solution {
    public List<Integer> iterativePreorder(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                result.add(current.val);
                current = current.right;
            } else {
                TreeNode temp = current.left;
                while (
                    (temp.right != null) && (temp.right != current)
                ) {
                    temp = temp.right;
                }

                if (temp.right == null) {
                    result.add(current.val);
                    temp.right = current;
                    current = current.left;
                } else {
                    temp.right = null;
                    current = current.right;
                }
            }
        }
        return result;
    }
}

The following Java solution outlines an approach to perform a Preorder Traversal on a binary tree using an iterative method:

• Create a LinkedList<Integer> named result that will store the values of visited nodes.

• Initialize a TreeNode pointer, named current, to the root of the tree.

• Use a while loop to traverse the tree, continuing until current is null.

• Inside the loop, check if the left child of current is null:

  • If true, add the value of current to the result list and move to its right child.
  • If the left child is not null, locate the rightmost node of the left subtree using a nested while loop:
    • Keep traversing to the right child of this subtree until a node is found that either has no right child or the right child is current.
  • After exiting the nested loop, there are two scenarios to address:
    • If the rightmost node's right pointer is null:
      • Add current's value to the result.
      • Set that node's right pointer to current to mark it as visited, then move current to its left child.
    • If the rightmost node's right pointer links back to current:
      • Set the right pointer of this node to null to restore the tree's structure.
      • Move to the right child of current.

• Finally, return the result list which now contains the Preorder traversal of the binary tree.

This method leverages the Morris traversal technique, which reduces the space complexity by avoiding the use of a stack, typically employed in recursive and other iterative approaches. This technique manipulates the tree's pointers to mark visited nodes, thereby eliminating the need for additional memory for traversal state.

int* preorder(struct TreeNode* root, int* size) {
    int* result = (int*)malloc(100 * sizeof(int));
    *size = 0;
    struct TreeNode* current = root;
    while (current != NULL) {
        if (current->left == NULL) {
            result[(*size)++] = current->val;
            current = current->right;
        } else {
            struct TreeNode* temp = current->left;
            while (temp->right != NULL && temp->right != current) {
                temp = temp->right;
            }
            if (temp->right == NULL) {
                result[(*size)++] = current->val;
                temp->right = current;
                current = current->left;
            } else {
                temp->right = NULL;
                current = current->right;
            }
        }
    }
    return result;
}

The provided C code defines a function preorder to perform a preorder traversal on a binary tree without using recursion. Instead, it uses a specific technique known as Morris Traversal, which manipulates the tree nodes to avoid using an auxiliary stack or recursion.

• The function signature, int* preorder(struct TreeNode* root, int* size), indicates it accepts a binary tree root and a pointer to track the size of the resulting array.
• An integer pointer result is allocated memory enough for 100 integers, expecting the binary tree could have up to 100 nodes. Adjust the allocated memory based on specific needs or implement dynamic resizing for better adaptability.
• The variable size represents the count of elements currently in the result array. Initialize *size to 0.
• A loop navigates the tree. If the current node's left child is absent, the node value is added to the result array and traversal moves to the right child.
• If the left child exists, the code finds the rightmost node in the left subtree that doesn't point back to the current node to avoid cycles.
• If this rightmost node has no threaded pointer to the current node (temp->right equals NULL), the current node's value is added to the result array and a temporary threaded link is created between this rightmost node and the current node. The traversal then moves left.
• If a threaded link exists indicating this subtree has been visited, it gets removed, and traversal shifts right.

This method provides an efficient way to traverse a binary tree without additional space overhead, such as recursion call stacks or extra data structures, by using the Morris Traversal technique.

var preorderTraversal = function (rootNode) {
    let results = [];
    let current = rootNode;
    while (current) {
        if (!current.left) {
            results.push(current.val);
            current = current.right;
        } else {
            let lastLeft = current.left;
            while (lastLeft.right && lastLeft.right !== current) {
                lastLeft = lastLeft.right;
            }
            if (!lastLeft.right) {
                results.push(current.val);
                lastLeft.right = current;
                current = current.left;
            } else {
                lastLeft.right = null;
                current = current.right;
            }
        }
    }
    return results;
};

This guide provides an overview of implementing a binary tree preorder traversal using JavaScript. The task involves using a non-recursive technique with the Morris Traversal method, optimizing the solution by not utilizing additional memory for recursion call stacks or stack data structures.

• Define a function preorderTraversal that accepts rootNode which represents the root of the tree.
• Initialize an array results to store the values of the nodes as you traverse the tree.
• Use a while loop to navigate through the nodes of the binary tree starting from the rootNode.
  • If the current node does not have a left child, push the value of the current node to results and move to the right child.
  • If the current node has a left child, find the rightmost node of the left subtree (but not return to the current node).
  • If the rightmost node does not link back to the current node, record the current node’s value, set its right pointer to the current node, then move to the left child of the current node.
  • If the rightmost node of the left subtree already links back to the current node, remove that link and move to its right child.
• Repeat this process until no nodes are left to visit.
• Return the results array containing the preorder traversal of the binary tree.

This method of binary tree traversal achieves the goal without using additional space for recursive stack frames or a separate stack, which makes it space-efficient, especially for large trees. This approach is particularly useful in scenarios where memory usage is a constraint.

class Solution:
    def preorder(self, root_node: TreeNode) -> List[int]:
        current, result = root_node, []
        while current:
            if not current.left:
                result.append(current.val)
                current = current.right
            else:
                pre = current.left

                while pre.right and pre.right is not current:
                    pre = pre.right

                if not pre.right:
                    result.append(current.val)
                    pre.right = current
                    current = current.left
                else:
                    pre.right = None
                    current = current.right

        return result

This Python3-based code snippet executes a Preorder Traversal on a binary tree. Preorder traversal, a common tree traversal technique, involves processing the root node before its child nodes. The code effectively leverages an iterative approach, utilizing Morris Traversal strategy, which optimizes memory usage by avoiding the use of a stack and modifying the tree structure during the traversal.

Understand the flow of the code:

• Initialize a current pointer to the root_node and result, an empty list that will store the values of the visited nodes.
• Use a while loop to traverse through the tree as long as current is not None.
• Inside the loop, if the current node does not have a left child, append its value to result and move to the right child.
• If a left child exists, find the rightmost node (referred as pre) of the left subtree.
• If pre.right is None, it means this subtree hasn't been fully traversed. Thus, set pre.right to current (creating a temporary thread back to the current node), record the value of current, and move current to its left child.
• If pre.right points back to the current node, it means the left subtree has been traversed. Therefore, remove the temporary thread by setting pre.right to None, and move current to its right child.
• Continue this process until all nodes are visited and the list result contains the values of the nodes in preorder sequence.

By the end of the traversal, the result list will contain the values of the nodes in the order they were visited. This technique is space efficient as it only requires space proportional to the depth of the tree, making it particularly useful for large trees.