Convert Binary Tree into Threaded Binary Tree

Problem

Given a binary tree write an algorithm to convert it into threaded binary tree.

In detail: A threaded binary tree is a binary tree in which all right pointers that normally would be null are repurposed to point to the inorder successor of the node, using an extra Boolean field to identify whether the right pointer is a thread or a regular binary tree link. The task here is to write an algorithm to convert a given binary tree into a threaded binary tree.

Examples

Example 1:

           4
          / \
         2   5
        / \
       1   3

Input: nums = [4, 2, 5, 1, 3]
Output: Nodes with threads: 1 → 2, 3 → 4
Explanation: 
- Node 1's right thread points to its inorder successor, 2.
- Node 3's right thread points to its inorder successor, 4.
- Node 4's right thread points to its inorder successor, 5.

graph TD
    D(4) --> B(2)
    D --> E(5)
    B --> A(1)
    B --> C(3)
    
    %% Adding right-thread connections:
    A -.->|Right Thread| B
    C -.->|Right Thread| D
    E ~~~ N1:::hidden

classDef hidden display:none
linkStyle 4 stroke:red,stroke-width:2px
linkStyle 5 stroke:red,stroke-width:2px

Note: Tree node has extra Boolean field to be used.

class TreeNode {
    int val;
    TreeNode left, right;
    boolean isThreaded; // True if right is a thread

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.isThreaded = false;
    }
}

Solution

As covered in the article threaded binary tree , a threaded binary tree has different types, and offers some advantages over normal binary tree.

This explanation focuses on converting a binary tree into a threaded binary tree, specifically a single-threaded one. Binary trees often have unused space because leaf nodes possess two null pointers. These pointers can be utilised to streamline inorder traversal without requiring recursion or a stack.

A single-threaded binary tree is structured so that each node either points to its inorder predecessor or successor through threads. In this case, all right null pointers will connect to the inorder successors, enabling faster traversal.

Solution

Method 1 - Inorder Traversal and queue

Perform an inorder traversal and store the sequence in a queue. Then, conduct a second traversal and update nodes with null right references to point to their successors retrieved from the queue.

Limitation: This method uses extra space for the queue and requires two traversals.

Method 2 - Reverse inorder traversal

To eliminate extra space and reduce the process to a single traversal:

1. Execute a reverse inorder traversal by visiting the right subtree first.
2. Maintain a reference to the previously visited node during recursion.
3. For a node with a null right pointer (and non-null previously visited node), update its right to point to the previous node and mark its 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.

Code

Java

public class Solution {
    static class TreeNode {
        int val;
        TreeNode left, right;
        boolean isThreaded; // True if right is a thread

        TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
            this.isThreaded = false;
        }
    }

    // Function to convert the binary tree into a threaded binary tree
    public void convertToThreaded(TreeNode root) {
        // Initial call to the helper function with no previous node (null)
        helper(root, null);
    }

    private TreeNode helper(TreeNode node, TreeNode previous) {
        if (node == null) {
            return previous; // Return the previous node (unchanged) if current node is null
        }

        // Traverse the right subtree first (reverse inorder traversal)
        previous = helper(node.right, previous);

        // If the current node's right pointer is null, thread it to the previous node
        if (node.right == null && previous != null) {
            node.right = previous;
            node.isThreaded = true; // Mark the right pointer as a thread
        }

        // Update the previous as the current node and traverse the left subtree
        previous = helper(node.left, node);

        return previous; // Return the last visited node for further recursion
    }

    // Helper Function to print the threaded binary tree in inorder traversal
    public void printInorder(TreeNode root) {
        TreeNode current = leftMost(root);
        while (current != null) {
            System.out.print(current.val + " ");
            // If the node is threaded, move to the inorder successor
            if (current.isThreaded) {
                current = current.right;
            } else {
                // Move to the left-most node in the right subtree
                current = leftMost(current.right);
            }
        }
    }

    private TreeNode leftMost(TreeNode node) {
        while (node != null && node.left != null) {
            node = node.left;
        }
        return node;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        // Convert binary tree to threaded binary tree
        sol.convertToThreaded(root);

        // Print inorder traversal of threaded binary tree
        System.out.println("Inorder Traversal of Threaded Binary Tree:");
        sol.printInorder(root);
    }
}

Python

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.isThreaded = False  # True if right is a thread

class Solution:
    def convertToThreaded(self, root):
        # Initial call to helper with no previous node (None)
        self._helper(root, None)

    def _helper(self, node, previous):
        if not node:
            return previous  # Return the previous node (unchanged) if current node is None

        # Traverse the right subtree first (reverse inorder traversal)
        previous = self._helper(node.right, previous)

        # If the current node's right pointer is null, thread it to the previous node
        if not node.right and previous:
            node.right = previous
            node.isThreaded = True  # Mark the right pointer as a thread

        # Update the previous node to the current node and traverse the left subtree
        previous = self._helper(node.left, node)

        return previous  # Return the last visited node for further recursion

    def inorderTraversal(self, root):
        # Helper function to print inorder traversal of the threaded binary tree
        current = self._leftMost(root)
        while current:
            print(current.val, end=" ")
            # If the node is threaded, move to the inorder successor
            if current.isThreaded:
                current = current.right
            else:
                # Move to the left-most node in the right subtree
                current = self._leftMost(current.right)

    def _leftMost(self, node):
        while node and node.left:
            node = node.left
        return node

# Example usage:
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

sol = Solution()
sol.convertToThreaded(root)
print("Inorder Traversal of Threaded Binary Tree:")
sol.inorderTraversal(root)

Complexity

• ⏰ Time complexity: O(n). Inorder traversal processes all n nodes exactly once.
• 🧺 Space complexity: O(h). Where h is the height of the tree, accounting for the recursive call stack during traversal.