Spread the post

Find nth ancestors of given two nodes in binary tree

Given a binary tree, Our goal is to find nth ancestor of given two nodes in binary tree. For example given Binary tree are contain following nodes.

132578946

Result

Explanation : N=3 node1=7 or node2=8 result=1.

1325789N=3 node1=7 , node2=846

View pointers and nodes of BT.

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

Try it Yourself

Program for find nth ancestors of binary tree without using recursion. Using a Queue.


Output

View process

Stack Areamainhead(pointer)root(pointer)tail(pointer)nth_ancestorauxiliary1(pointer)auxiliary2(pointer)counter (int) =1head(pointer)node1 (int) =6node2 (int) =7nth (int) =3status (int) =0temp(pointer) Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer) right (pointer) struct Treedata (int)= 3left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 4left (pointer)= NULLright (pointer) struct Treedata (int)= 5left (pointer) right (pointer) struct Treedata (int)= 6left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 7left (pointer)= NULLright (pointer) struct Treedata (int)= 8left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 9left (pointer)= NULLright (pointer)= NULLstruct Queuelevel (int)= 0link (pointer) parent (pointer)= NULLnext (pointer) struct Queuelevel (int)= 1link (pointer) parent (pointer) next (pointer) struct Queuelevel (int)= 1link (pointer) parent (pointer) next (pointer) struct Queuelevel (int)= 2link (pointer) parent (pointer) next (pointer) struct Queuelevel (int)= 2link (pointer) parent (pointer) next (pointer) struct Queuelevel (int)= 3link (pointer) parent (pointer) next (pointer) struct Queuelevel (int)= 3link (pointer) parent (pointer) next (pointer) struct Queuelevel (int)= 3link (pointer) parent (pointer) next (pointer) struct Queuelevel (int)= 4link (pointer) parent (pointer) next (pointer)= NULL

Try it Yourself

Spread the post

Recommended Posts: