Can I do inorder traversal of a binary tree without recursion and stack?

Question

Can anyone give me a solution for traversing a binary tree in inorder without recursion and without using a stack?

Answer 1

Second edit: I think this is right. Requires node.isRoot, node.isLeftChild, and node.parent, in addition to the usual node.left_child and node.right_child.

state = "from_parent"
current_node = root
while (!done)
  switch (state)
    case "from_parent":
      if current_node.left_child.exists
        current_node = current_node.left_child
        state = "from_parent"
      else
        state = "return_from_left_child"
    case "return_from_left_child"
      if current_node.right_child.exists
        current_node = current_node.right_child
        state = "from_parent"
      else
        state = "return_from_right_child"
    case "return_from_right_child"
      if current_node.isRoot
        done = true
      else
        if current_node.isLeftChild
         state = "return_from_left_child"
        else
         state = "return_from_right_child"
        current_node = current_node.parent

Answer 2

1. Double threaded tree

If your tree nodes have parent references/pointers, then keep track of which you node you came from during the traversal, so you can decide where to go next.

In Python:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = None
        if self.left:
            self.left.parent = self
        if self.right:
            self.right.parent = self

    def inorder(self):
        cur = self
        pre = None
        nex = None
        while cur:
            if cur.right and pre == cur.right:
                nex = cur.parent
            elif not cur.left or pre == cur.left:
                yield cur.value  # visit!
                nex = cur.right or cur.parent
            else:
                nex = cur.left
            pre = cur
            cur = nex

root = Node(1,
            Node(2, Node(4), Node(5)),
            Node(3)
        )

print([value for value in root.inorder()])  # [4, 2, 5, 1, 3]

2. Single threaded tree

If your tree nodes do not have parent references/pointers, then you can do a so-called Morris traversal, which temporarily mutates the tree, making the right property -- of a node that has no right child -- temporarily point to its inorder successor node:

In Python:

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

    def inorder(self):
        cur = self
        while cur:
            if cur.left:
                pre = cur.left
                while pre.right:
                    if pre.right is cur:
                        # We detect our mutation. So we finished
                        # the left subtree traversal.
                        pre.right = None
                        break
                    pre = pre.right
                else:  # prev.right is None
                    # Mutate this node, so it links to curr
                    pre.right = cur
                    cur = cur.left
                    continue
            yield cur.value
            cur = cur.right

root = Node(1,
            Node(2, Node(4), Node(5)),
            Node(3)
        )

print([value for value in root.inorder()])