treetree-traversal

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


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


Solution

  • 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