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

Spread the post

Print all complete binary tree nodes

Write an efficient algorithm to print complete binary tree nodes. If Given tree is complete Binary tree then print all elements. Otherwise print some nodes which of satisfied the property of complete Binary tree.

Complete binary tree properties.

1) Level-1 nodes are completely found.

2) Bottom level nodes are exist of left to right completely found.

Example 1

Suppose following nodes are inserted on binary tree.

132564

In this tree are complete binary tree. then print all nodes.

Example 2

Suppose following nodes are inserted on binary tree.

13682574

look at this tree there are not complete binary tree. In this case print following elements.

13254

Print nodes [1,2,3,4,5].

discard following nodes [6,7,8].

Consider example 2

View Nodes and pointers.

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

Try it Yourself

Program for print all complete Binary tree nodes which are satisfied complete binary tree property. iterative solution using Queue.


Output

Visualize process.

Stack Areamainhead(pointer)root(pointer)print_complete_btauxiliary(pointer)flag (int) =1head(pointer)root(pointer)status (int) =0tail(pointer)dequeuehead(pointer)remove(pointer) Heap Areastruct Treedata (int)= 1left (pointer) right (pointer) struct Treedata (int)= 2left (pointer) right (pointer) struct Treedata (int)= 3left (pointer)= NULLright (pointer) struct Treedata (int)= 4left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 5left (pointer)= NULLright (pointer) struct Treedata (int)= 6left (pointer)= NULLright (pointer) struct Treedata (int)= 7left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 8left (pointer)= NULLright (pointer)= NULLstruct Queuelink (pointer)= NULLnext (pointer) struct Queuelink (pointer) next (pointer)= NULL

Visualize process Try it Yourself

Spread the post

Recommended Posts: