The Vakhnin Algorithm: Left-Side Tree Traversal with O(1) Memory

The Vakhnin Algorithm: Left-Side Tree Traversal with O(1) Memory

Key Elements of the Tree

Terminator (T)

Terminator is the last node in a subtree encountered during the left-side traversal.

Parent of the Next Subtree (PNS)

PNS is the node to which the algorithm returns after finishing the traversal of the left subtree.

Pointer to the Current PNS

A pointer that temporarily stores a reference to PNS in order to ensure the transition to the right subtree.

Marker Node (M)

M is a service node written into the right pointer of T to mark the end of the current subtree.

Searching for the Terminator

The search for T starts from the root of a subtree. The algorithm moves through the tree as follows:

1. If the current node has a right branch, move to its child.
2. If there is no right branch, move to the left branch.
3. If the node has no children (both pointers are empty), this node is the Terminator (T).

Tree Diagram with Terminator and Service Elements

Step-by-Step Process of Searching for the Terminator

1. Start from the root of the subtree (5).
2. Move to the right child (7), since the current node has a right branch.
3. Node 7 has no right branch, but it has a left one. Move to the left child (9).
4. Node 9 has both children. Move to the right child (6).
5. Node 6 has no children (both pointers are empty) — this is the Terminator (T).

Setting and Resetting Terminator Links

1. At the first visit (setting links):

   • Right pointer: redirected to M.
   • Left pointer: redirected to the pointer to the current PNS.

2. At the second visit (resetting links):

   • Left and right pointers are restored to their initial state (set to empty).

Traversal Algorithm

Initialization

1. Setting the initial node:
   
   The algorithm starts from the root of the tree, which becomes the current node for processing.

2. Pointer to the current parent of the next subtree (PNS):
   
   This pointer is initially empty. Transitioning to this empty pointer signals the end of the algorithm.

3. Creating the Marker Node:
   
   The Marker Node is used to mark the end of the current subtree (T) and helps manage the return to PNS.

Traversal Process

For each node:

• Process the node by adding its value to the result.
• If the node has only one child, move to it.
• If the node has both children, or if the node is T after a service pass (after the service pass, T has both pointers non-empty):
  • If the node is T after a service pass:
  • Recognized by the presence of M in its right pointer.
  • Save the left pointer, which stores the pointer to the current PNS.
  • Reset both left and right pointers to empty.
  • Continue the algorithm from the PNS saved in the left pointer.
  • If the node is not T:
  • Find T in the left subtree of the current node.
  • Write the Marker Node (M) into the right pointer of the found T to mark the end of the current subtree.
  • Write the current PNS into the left pointer of the found T to ensure the return after finishing the left subtree traversal.

State After Traversal

• All nodes of the tree are processed.
• Left and right pointers of all T nodes are restored to their original state.
• All service elements, such as markers and temporary links, are removed.
• The tree structure is fully restored and identical to its initial state.
• The traversal result is represented as a sequence of node values corresponding to the full left-side traversal.

Python Implementation of Full Left-Side Traversal of a Binary Tree

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


path = []


def process_node(node):
    # Processes a tree node by adding its value to the global path list.
    path.append(node.value)


def traverse_tree(root):
    # Performs a custom traversal of the tree using markers.
    def get_terminator(root):
        # Finds the terminator — the rightmost node in the subtree
        while root and (root.left or root.right):
            root = root.right if root.right else root.left
        return root

    marker = TreeNode("Marker")

    while root:
        process_node(root)
        if root.left is marker:  # Second visit to the terminator
            root_right = root.right  # Save the root of the right subtree
            root.left = None  # Break the service link (marker)
            root.right = None  # Break the link to the right subtree
            root = root_right  # Move to process the right subtree
        elif root.left and root.right:
            terminator = get_terminator(root.left)
            terminator.left = marker  # Set the marker
            terminator.right = root.right  # Save the link to the right subtree
            root = root.left
        else:
            root = root.left if root.left else root.right

Full version of the code with tests available on GitHub Gist:

Vakhnin Algorithm - Full Implementation with Tests