isThreaded flag as true.
Important considerations include keeping the previous reference unchanged during recursive calls to the right subtree and updating it when traversing the left subtree.
convert-binary-tree-into-threaded-binary-tree-viz1.excalidraw
Code

[{"language":"Java","code":"public class Solution {\n    static class TreeNode {\n        int val;\n        TreeNode left, right;\n        boolean isThreaded; // True if right is a thread\n\n        TreeNode(int val) {\n            this.val = val;\n            this.left = null;\n            this.right = null;\n            this.isThreaded = false;\n        }\n    }\n\n    // Function to convert the binary tree into a threaded binary tree\n    public void convertToThreaded(TreeNode root) {\n        // Initial call to the helper function with no previous node (null)\n        helper(root, null);\n    }\n\n    private TreeNode helper(TreeNode node, TreeNode previous) {\n        if (node == null) {\n            return previous; // Return the previous node (unchanged) if current node is null\n        }\n\n        // Traverse the right subtree first (reverse inorder traversal)\n        previous = helper(node.right, previous);\n\n        // If the current node's right pointer is null, thread it to the previous node\n        if (node.right == null && previous != null) {\n            node.right = previous;\n            node.isThreaded = true; // Mark the right pointer as a thread\n        }\n\n        // Update the previous as the current node and traverse the left subtree\n        previous = helper(node.left, node);\n\n        return previous; // Return the last visited node for further recursion\n    }\n\n    // Helper Function to print the threaded binary tree in inorder traversal\n    public void printInorder(TreeNode root) {\n        TreeNode current = leftMost(root);\n        while (current != null) {\n            System.out.print(current.val + \" \");\n            // If the node is threaded, move to the inorder successor\n            if (current.isThreaded) {\n                current = current.right;\n            } else {\n                // Move to the left-most node in the right subtree\n                current = leftMost(current.right);\n            }\n        }\n    }\n\n    private TreeNode leftMost(TreeNode node) {\n        while (node != null && node.left != null) {\n            node = node.left;\n        }\n        return node;\n    }\n\n    public static void main(String[] args) {\n        Solution sol = new Solution();\n\n        TreeNode root = new TreeNode(4);\n        root.left = new TreeNode(2);\n        root.right = new TreeNode(5);\n        root.left.left = new TreeNode(1);\n        root.left.right = new TreeNode(3);\n\n        // Convert binary tree to threaded binary tree\n        sol.convertToThreaded(root);\n\n        // Print inorder traversal of threaded binary tree\n        System.out.println(\"Inorder Traversal of Threaded Binary Tree:\");\n        sol.printInorder(root);\n    }\n}","lang":"java"},{"language":"Python","code":"class TreeNode:\n    def __init__(self, val=0):\n        self.val = val\n        self.left = None\n        self.right = None\n        self.isThreaded = False  # True if right is a thread\n\nclass Solution:\n    def convertToThreaded(self, root):\n        # Initial call to helper with no previous node (None)\n        self._helper(root, None)\n\n    def _helper(self, node, previous):\n        if not node:\n            return previous  # Return the previous node (unchanged) if current node is None\n\n        # Traverse the right subtree first (reverse inorder traversal)\n        previous = self._helper(node.right, previous)\n\n        # If the current node's right pointer is null, thread it to the previous node\n        if not node.right and previous:\n            node.right = previous\n            nod
Related Tags
