Binary Tree Inorder Traversal

class Solution {
public:
    vector<int> inorderTreeTraversal(TreeNode* root) {
        vector<int> output;
        TreeNode* current = root;
        TreeNode* precursor;

        while (current != nullptr) {
            if (current->left == nullptr) {
                output.push_back(current->val);
                current = current->right;
            } else {
                precursor = current->left;
                while (precursor->right != nullptr && precursor->right != current) {
                    precursor = precursor->right;
                }

                if (precursor->right == nullptr) {
                    precursor->right = current;
                    current = current->left;
                } else {
                    precursor->right = nullptr;
                    output.push_back(current->val);
                    current = current->right;
                }
            }
        }
        return output;
    }
};

The provided C++ code demonstrates an approach to the binary tree inorder traversal using a well-known algorithm known as Morris Traversal. This algorithm effectively traverses a binary tree without using recursion or additional memory for a stack, making it space-efficient with O(1) extra space complexity.

Here’s a breakdown of the approach:

• Initialize a vector, output, to store the value of nodes in inorder sequence.
• Use a current pointer to traverse the tree, starting from the root.
• Use another pointer called precursor to find the inorder predecessor of the current node.

The Steps in the Morris Traversal Algorithm

1. While the current node is not NULL:
   • Check if the current node's left child is NULL.
     • If true, add the current’s value to the output. Move to the right child of the current.
   • If the left child is not NULL:
     • Set precursor to the left child of current.
     • Move precursor to its rightmost child that is not linked back to the current node (These links are temporarily made in this algorithm to remember the path without using extra memory).
     • If the right child of precursor is NULL:
       • Make its right child point back to current (temporary threading of the tree), and move current to its left child.
     • If the right child of precursor points to current:
       • Remove the temporary link (set precursor’s right child to NULL), add current's value to output, and move current to its right child.

This traversal ensures that each node's left subtree is visited before the node itself and finally its right subtree, adhering to the inorder traversal requirement. The beauty of this solution lies in its efficiency and lower memory requirement, making it optimal for situations where memory usage is a critical concern.

class Solution {
    public List<Integer> inorder(TreeNode root) {
        List<Integer> output = new ArrayList<>();
        TreeNode current = root;
        TreeNode predecessor;

        while (current != null) {
            if (current.left == null) {
                output.add(current.val);
                current = current.right;
            } else {
                predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    predecessor.right = current;
                    current = current.left;
                } else {
                    predecessor.right = null;
                    output.add(current.val);
                    current = current.right;
                }
            }
        }

        return output;
    }
}

The solution implements an iterative method for Inorder Traversal of a Binary Tree using Java. Here's a succinct breakdown of the logic employed in the provided code:

• Begin with the root of the binary tree.
• Use a while loop to process nodes until there are no more nodes to process (current != null).
• Inside the loop, check if the left child of the current node is null:
  • If true, add the current node's value to the output list and proceed to the right child.
• If the left child is not null, find the rightmost node of the left subtree, termed as predecessor.
  • Traverse to this predecessor node using a nested while loop until its right child is null or the current node itself.
  • Then:
    • If predecessor.right is null, establish a temporary thread (Morris threading) to the current node and move to the left child of the current.
    • If predecessor.right points to the current node, it indicates a return to a threaded node, hereby, remove the temporary thread and:
      • Add the current node's value to output.
      • Move to the right child of the current node.
• The traversal continues until all nodes are processed, and the function returns the output list containing the values in Inorder sequence.

This approach reduces the space complexity by avoiding the use of a stack, typically used in recursive and iterative deep tree traversals, by utilizing a threading technique known as Morris Traversal to link the tree nodes temporarily.

function TreeNode(value, leftChild, rightChild) {
    this.value = (value === undefined ? 0 : value);
    this.left = (leftChild === undefined ? null : leftChild);
    this.right = (rightChild === undefined ? null : rightChild);
}

function inorder(root) {
    let result = [];
    let current = root;
    let predecessor;

    while (current != null) {
        if (current.left == null) {
            result.push(current.value);
            current = current.right; // Move right
        } else {
            predecessor = current.left;
            while (predecessor.right !== null && predecessor.right !== current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right === null) {
                // Make a temporary link to current
                predecessor.right = current;
                current = current.left;
            } else {
                // Revert the changes made in the tree
                predecessor.right = null;
                result.push(current.value);
                current = current.right;
            }
        }
    }

    return result;
}

To perform an inorder traversal on a binary tree using JavaScript, you utilize the Morris Traversal method. This approach eliminates the need for an auxiliary stack or recursion, making it memory efficient, particularly useful for large trees.

Solution Breakdown:

• TreeNode Structure:

  • Define a TreeNode function to create nodes of the binary tree. Each node might include a value and pointers to its left and right children.

• Inorder Traversal Function:

  • Define the inorder function that accepts the root of the tree as its parameter and returns an array of values representing the inorder traversal.
  • Initialize an empty array result to store the traversal result.
  • Use a current pointer to navigate through the tree, starting at the root.

• Traversal Process:

  • Traverse the tree using a while loop until the current pointer is null.
  • If the current node (current) has no left child, append its value to result and move to the right child.
  • If the current node has a left child, find the inorder predecessor of the current node in its left subtree (the rightmost node in the left subtree).
  • If the predecessor's right pointer is null, set it temporarily to the current node, facilitating a return after visiting the left subtree, then move the current to its left child.
  • If the predecessor's right pointer points to the current node, it indicates that the left subtree has been fully visited. At this point, break this temporary link to restore the tree's original structure, append the current node's value to result, and move to the right child.

• Output:

  • After exiting the loop, the result array contains the values of the nodes in inorder sequence.

The Morris Traversal method offers an efficient way to traverse a tree without additional space for recursion stack or other data structures. This makes it particularly suitable for scenarios where space efficiency is a priority.

function TreeNode(value, leftChild, rightChild) {
    this.value = (value === undefined ? 0 : value);
    this.left = (leftChild === undefined ? null : leftChild);
    this.right = (rightChild === undefined ? null : rightChild);
}

function inorder(root) {
    let result = [];
    let current = root;
    let predecessor;

    while (current != null) {
        if (current.left == null) {
            result.push(current.value);
            current = current.right; // Move right
        } else {
            predecessor = current.left;
            while (predecessor.right !== null && predecessor.right !== current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right === null) {
                // Make a temporary link to current
                predecessor.right = current;
                current = current.left;
            } else {
                // Revert the changes made in the tree
                predecessor.right = null;
                result.push(current.value);
                current = current.right;
            }
        }
    }

    return result;
}

class Solution:
    def inorder(self, node: TreeNode) -> List[int]:
        output = []
        current = node

        while current is not None:
            if current.left is None:
                output.append(current.val)
                current = current.right
            else:
                predecessor = current.left
                while predecessor.right and predecessor.right != current:
                    predecessor = predecessor.right

                if predecessor.right is None:
                    predecessor.right = current
                    current = current.left
                else:
                    predecessor.right = None
                    output.append(current.val)
                    current = current.right

        return output

The given Python solution details a non-recursive approach for performing an inorder traversal of a binary tree using Morris traversal technique. Implement this method to ensure effective traversal without the use of additional memory (like recursion stack or an explicit stack data structure). Follow these steps to understand the operations:

1. Initialize with the root node.

2. Use a loop to traverse through the nodes while the current node is not None.

3. Inside the loop, check if the current.left is None. If it is, append the current.val to the output and move to the current.right.

4. If current.left is not None, initiate another traversal to find the rightmost node of the left subtree (predecessor).

5. Ensure in this inner loop that you stop when predecessor.right is either None or equal to current.

6. Update the right pointer of the predecessor:

   • If predecessor.right is None, direct it towards current, and shift the current pointer to current.left.
   • If predecessor.right points to current, reset it to None, append current.val to output, then move to current.right.

7. When the outer loop completes, the output list contains the inorder traversal of the tree.

Remember, this Morris Traversal method modifies the tree by temporarily adding additional pointers but ensures to restore the tree back to its original structure as the algorithm proceeds. Adhere to this technique for an optimized traversal of a binary tree, especially in environments where memory efficiency is critical.