Is it possible to traverse a binary tree without recursion and stack?

Question

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

Answer 1

Second edit: I think this is correct. 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

Since some state is required to move the binary tree (nodes return after visiting successors), which can be provided by the stack, implied by recursion (or an explicit array).

The answer is no, you cannot. (according to the classical definition)

The closest thing to iterate through the binary tree is probably using heap

EDIT: Or as the threaded binary tree is already shown,

Answer 3

Yes, you can. To do this, you will need a parent pointer to climb the tree.

Answer 4

Start with tree_first (), continue with tree_next () until you get NULL. Full code: https://github.com/virtan/tree_closest

 struct node { int value; node *left; node *right; node *parent; }; node *tree_first(node *root) { while(root && root->left) root = root->left; return root; } node *tree_next(node *p) { if(p->right) return tree_first(p->right); while(p->parent) { if(!p->parent->right || p->parent->right != p) return p->parent; else p = p->parent; } return 0; } 

Answer 5

As already mentioned here, this is possible, but not without a parent pointer. The source pointer basically lets you navigate the "path" if you want, and therefore print the nodes. But why does recursion work without a parent pointer? Well, if you understand recursion, it looks something like this (imagine a recursion stack):

  recursion //going into recursion recursion recursion recursion //going back up recursion recursion recursion 

So, when the recursion ends, you printed the selected side of the binary tree in reverse order.