Spread the post

Print path from leaf to root in binary tree

Print full paths from bottom to top in binary tree without recursion. using stack.

For example Given Binary tree are contain following nodes.

12475836910

Result

Hint: Using Inorder tree traversal methods. if find leaf node then print all element of stack.

View pointers and nodes of tree.

Stack Areamainhead(pointer) NULLroot(pointer)top(pointer) NULL Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer) right (pointer) struct Treedata (int)= 3left (pointer)= NULLright (pointer) struct Treedata (int)= 4left (pointer) right (pointer)= NULLstruct Treedata (int)= 5left (pointer)= NULLright (pointer) struct Treedata (int)= 6left (pointer) right (pointer)= NULLstruct Treedata (int)= 7left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 8left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 9left (pointer)= NULLright (pointer) struct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULL

Try it Yourself

C program for print all leaf to root paths of given binary tree. Time complexity O(n).


Output

View process

Stack Areamainroot(pointer)top(pointer)path_printstore(pointer)temp(pointer)top(pointer) Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer) right (pointer) struct Treedata (int)= 3left (pointer)= NULLright (pointer) struct Treedata (int)= 4left (pointer) right (pointer)= NULLstruct Treedata (int)= 5left (pointer)= NULLright (pointer) struct Treedata (int)= 6left (pointer) right (pointer)= NULLstruct Treedata (int)= 7left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 8left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 9left (pointer)= NULLright (pointer) struct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULLstruct Stackvisit (int)= 2link (pointer) next (pointer)= NULLstruct Stackvisit (int)= 2link (pointer) next (pointer) struct Stackvisit (int)= 1link (pointer) next (pointer)

Try it Yourself

Spread the post

Recommended Posts: