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

Spread the post

Diameter of a binary tree

Diameter of Binary tree is longest path between two nodes. Write an efficient algorithm to find diameter of binary tree .

Example

Suppose following nodes are inserted on binary tree.

123468579

Result : Diameter is 7

123468579

Longest path from two nodes.

View Nodes and pointers.

Stack Areamainresult (int) =0root(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) right (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 how to find the diameter of a binary tree. iterative recursion time complexity O(n).


Output

Visualize process.

Stack Areamainresult (int) =3root(pointer)diametera (int) =1b (int) ? result(pointer)temp(pointer)diametera (int) =3b (int) ? result(pointer)temp(pointer)diametera (int) =0b (int) ? result(pointer)temp(pointer)diametera (int) =0b (int) ? result(pointer)temp(pointer)diametera (int) ? b (int) ? result(pointer)temp(pointer)diameterresult(pointer)temp(pointer) NULL 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) right (pointer)= NULLstruct Treedata (int)= 7left (pointer)= NULLright (pointer) struct Treedata (int)= 8left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 9left (pointer)= NULLright (pointer)= NULL

Visualize process Try it Yourself

Spread the post

Recommended Posts: