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

Spread the post

Find n-th node of inorder traversal

Write an efficient program to print the nth node of inorder traversal. for example.

For example

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

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

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=3

1237456

View process.

Stack Areamainroot(pointer)find_positionhead(pointer)nth (int) =3result (int) =0findhead(pointer)nth (int) =3result(pointer)findhead(pointer)nth (int) =3result(pointer)findhead(pointer)nth (int) =3result(pointer)findhead(pointer)nth (int) =3result(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 print nth node of inorder traversal.Time complexity O(n).


Output

Submit your solution in comment.

Spread the post

Recommended Posts: