# Monthly Archives: October 2015

## Convert to sum tree by post-order threaded binary tree

Original problem is from g4g: link. And I solved it by recursion: link

But further problem is given by Abdul Rais, which requires to convert sum tree by post-order threaded binary tree. At first glance, I don’t know how does post-order threaded binary tree look like. I’ve only seen in-order threaded binary tree.

In order to find the successor in post-order-traversal in O(1) time, I added a successor for each tree node. In this way, for each specific tree, it has a starting node. In order to manage the tree, I created a TreeManager structure.

Building a post-order-threaded binary tree is like a common thing. We need a indicator to tell is a node has ever been visited.

In order to convert to sum tree, we need to store old value for parent calculation. So in tree structure, I added a oldValue variable.

Check my code on github: link

## Convert to sum tree by post-order threaded binary tree

Original problem is from g4g: link. And I solved it by recursion: link

But further problem is given by Abdul Rais, which requires to convert sum tree by post-order threaded binary tree. At first glance, I don’t know how does post-order threaded binary tree look like. I’ve only seen in-order threaded binary tree.

In order to find the successor in post-order-traversal in O(1) time, I added a successor for each tree node. In this way, for each specific tree, it has a starting node. In order to manage the tree, I created a TreeManager structure.

Building a post-order-threaded binary tree is like a common thing. We need a indicator to tell is a node has ever been visited.

In order to convert to sum tree, we need to store old value for parent calculation. So in tree structure, I added a oldValue variable.

Check my code on github: link