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

Since traversing a binary tree requires some kind of state (nodes to return after visiting successors) which could be provided by stack implied by recursion (or explicit by an array).

The answer is no, you can't. (according to the classic definition)

The closest thing to a binary tree traversal in an iterative way is probably using a heap

EDIT: Or as already shown a threaded binary tree ,

Answer 2

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 3

Yes, you can. In order to do this, you would require a parent pointer in order to ascend the tree.