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

Spread the post

Find distance between two nodes of a Binary Tree

Given a binary tree, Our goal is to find minimum (shortest) distance between two nodes in a binary tree.

For example given Binary tree are contain following nodes.

132578946

Result

Note that distance are calculate by number of edges are exist, between two given nodes.

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 shortest distance between two nodes in a binary tree without using recursion. Using a Queue.


Output

View process

Stack Areamainhead(pointer)root(pointer)tail(pointer)find_distanceauxiliary1(pointer)auxiliary2(pointer) NULLdistance (int) =0head(pointer)node1 (int) =4node2 (int) =9temp(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: