Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

Inorder binary tree traversal without recursion

Inorder tree traversal without using recursion. Simplest method are using a stack. and perform inorder tree traversal.

Suppose following node are contain in binary tree.

1243893010

Inorder : 4 2 1 8 10 3 9 30

Inorder traversal using stack.

View pointers and code execution process.

Stack Areamainroot(pointer)top(pointer) NULL Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer) right (pointer)= NULLstruct Treedata (int)= 3left (pointer) right (pointer) struct Treedata (int)= 4left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 8left (pointer)= NULLright (pointer) struct Treedata (int)= 9left (pointer)= NULLright (pointer) struct Treedata (int)= 30left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULL

view stack pointers.

Stack Areamainroot(pointer)top(pointer)inorder_traversaltemp(pointer)top(pointer)popremove(pointer)top(pointer) Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer) right (pointer)= NULLstruct Treedata (int)= 3left (pointer) right (pointer) struct Treedata (int)= 4left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 8left (pointer)= NULLright (pointer) struct Treedata (int)= 9left (pointer)= NULLright (pointer) struct Treedata (int)= 30left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULLstruct Stacklink (pointer) next (pointer)= NULLstruct Stacklink (pointer) next (pointer)

Try it Yourself

C program for inorder traversal of binary tree. time complexity O(n).


Output

Spread the post

Recommended Posts: