Spread the post

Sum of all left leaves nodes of given binary tree

Write an efficient algorithm to sum of all existing left leaves node in given binary tree. solving of this problem using recursion are very easy. but here given a iterative solution using stack.

Suppose following nodes are inserted on binary tree.

13682574

Result :Sum of all left leaves is 11

View left leaf nodes.

13682574

Iterative solution : This given below function accept two parameter.

a) root node of tree and

b) address of stack pointer

Preorder traversal of tree in iterative manner and add this node value.

View nodes and pointers.

Stack Areamainroot(pointer)top(pointer) NULL 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) right (pointer)= NULLstruct 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 Sum of all left leaves nodes in existing binary tree.. iterative solution using stack.


Output

Visualize process.

Stack Areamainroot(pointer)top(pointer)left_lsumauxilary(pointer) NULLsum (int) =11temp(pointer) NULLtop(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) right (pointer)= NULLstruct Treedata (int)= 6left (pointer)= NULLright (pointer) struct Treedata (int)= 7left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 8left (pointer)= NULLright (pointer)= NULLstruct Stacklink (pointer) next (pointer)= NULLstruct Stacklink (pointer) next (pointer) struct Stacklink (pointer) next (pointer)

Visualize process Try it Yourself

Exercise Solve this problem using inorder and postorder traversal.

Spread the post

Recommended Posts: