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

Spread the post

Find n-th node of postorder traversal

Write an efficient program to print the nth node of postorder traversal.

For example

Suppose Binary tree contain following nodes [1,2,3,4,5,6,7].

1237456Postorder : 2, 6, 5, 4, 7, 3, 1

Given position, and get the node of this position.

View nodes of this tree.

Stack Areamainroot(pointer) Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 3left (pointer) right (pointer) struct Treedata (int)= 4left (pointer) right (pointer)= NULLstruct Treedata (int)= 5left (pointer)= NULLright (pointer) struct Treedata (int)= 6left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 7left (pointer)= NULLright (pointer)= NULL

Suppose n=7

1237456

View process.

Stack Areamainroot(pointer)find_positionhead(pointer)nth (int) =5result (int) =5findhead(pointer)nth (int) =5result(pointer)findhead(pointer)nth (int) =5result(pointer)findhead(pointer)nth (int) =5result(pointer) Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 3left (pointer) right (pointer) struct Treedata (int)= 4left (pointer) right (pointer)= NULLstruct Treedata (int)= 5left (pointer)= NULLright (pointer) struct Treedata (int)= 6left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 7left (pointer)= NULLright (pointer)= NULL

Visualize process Try it Yourself

Program to find nth node of postorder traversal. Time complexity O(n).


Output

Submit your solution in comment.

Spread the post

Recommended Posts: